Submission #3435231


Source Code Expand

/*+lmake
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
struct debugger
{
    template <typename T>
    debugger &operator,(const T &v)
    {
		std::cerr << v << " ";
        return *this;
    }
} dbg;

void iopen()
{
    static bool isOpen = false;
    if (!isOpen) {
        isOpen = true;
#ifdef WAAUTOMATON
        freopen("in.txt", "r", stdin);
#endif
    }
}
template <size_t _I_Buffer_Size = 1 << 23, size_t _O_Buffer_Size = 1 << 23>
struct IO_Tp
{
    char _I_Buffer[_I_Buffer_Size];
    char *_I_pos;
    const char *_I_end;

    char _O_Buffer[_O_Buffer_Size];
    char *_O_pos;
    const char *_O_end;

    IO_Tp()
        : _I_pos(_I_Buffer)
        , _O_pos(_O_Buffer)
        , _I_end(_I_Buffer + _I_Buffer_Size)
        , _O_end(_O_Buffer + _O_Buffer_Size)
    {
    }

    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    inline char getchar()
    {
        char res = *_I_pos;
        nextchar();
        return res;
    }

    inline bool is_digit(const char ch) { return '0' <= ch && ch <= '9'; }

    inline void nextchar()
    {
        ++_I_pos;
        if (_I_pos == _I_end) {
            fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
            _I_pos = _I_Buffer;
        }
    }

    template <typename Int>
    inline IO_Tp &operator>>(Int &res)
    {
        res = 0;
        int k = 1;
        while (!is_digit(*_I_pos)) {
            if (*_I_pos == '-')
                k = -1;
            nextchar();
        }
        do {
            (res *= 10) += (*_I_pos) -'0';
            nextchar();
        } while (is_digit(*_I_pos));
        res *= k;
        return *this;
    }

    inline IO_Tp &operator>>(char &res)
    {
        res = *_I_pos;
        nextchar();
        return *this;
    }

	inline void putchar(char x)
	{
		if (_O_pos==_O_end) {
			fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);
			_O_pos=_O_Buffer;
		}
		*_O_pos++=x;
	}
    template <typename Int>
    inline IO_Tp &operator<<(Int n)
    {
        if (n < 0) {
			putchar('-');
            n = -n;
        }
        static char _buf[20];
        char *_pos(_buf);
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf)
            putchar(*--_pos);
        return *this;
    }

    inline IO_Tp &operator<<(char ch)
    {
		putchar(ch);
        return *this;
    }

	inline IO_Tp &operator<<(const char* s)
	{
		while(*s!=0) {
			putchar(*s);
			++s;
		}
		return *this;
	}
};
IO_Tp<> IO;
const int MAXN=200000;
int a[MAXN+10],b[MAXN+10];
struct Point
{
	int x,y;
}p[MAXN+10];
int tong[MAXN+10];
const LL kcz=1e9+7;
LL t[MAXN+10];
void add(int p,LL v,int n)
{
	for(int i=p; i<=n; i+=i&(-i)) {
		t[i]+=v;
		t[i]%=kcz;
	}
}
LL query(int p)
{
	LL ans=0;
	for(int i=p; i>0; i-=i&(-i)) {
		ans+=t[i];	
	}
	return ans%kcz;
}
int main()
{
	iopen();
	int n,m;
	IO>>n>>m;
	for(int i=1; i<=n; ++i) {
		IO>>a[i];
	}
	for(int i=1; i<=m; ++i) {
		IO>>b[i];
	}
	int cnt=0;
	for(int i=1; i<=n; ++i) {
		int t=lower_bound(b+1,b+1+m,a[i])-b;
		if (t==1 || t==m+1) continue;
		++cnt;
		p[cnt].y=*lower_bound(b+1,b+1+m,a[i])-a[i];
		p[cnt].x=a[i]-*(upper_bound(b+1,b+1+m,a[i])-1);
		tong[cnt]=p[i].y;
	}
	n=cnt;
	sort(tong+1,tong+1+n);
	m=unique(tong+1,tong+1+n)-tong-1;
	for(int i=1; i<=n; ++i) {
		p[i].y=lower_bound(tong+1,tong+1+m,p[i].y)-tong;
	}
	sort(p+1,p+1+n,[](const Point& a,const Point& b){if (a.x==b.x) return a.y>b.y; return a.x<b.x;});
	n=unique(p+1,p+1+n,[](const Point& a,const Point& b){return a.x==b.x && a.y==b.y;})-p-1;
	LL ans=0;
	for(int i=1; i<=n; ++i) {
		LL now=1+query(p[i].y-1);
		ans+=now;
		ans%=kcz;
		add(p[i].y,now,m+1);
	}
	cout<<ans+1<<endl;
    return 0;
}

Submission Info

Submission Time
Task F - Robots and Exits
User WAAutoMaton2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4509 Byte
Status WA
Exec Time 54 ms
Memory 9600 KB

Compile Error

./Main.cpp: In member function ‘void IO_Tp<_I_Buffer_Size, _O_Buffer_Size>::nextchar() [with long unsigned int _I_Buffer_Size = 8388608ul; long unsigned int _O_Buffer_Size = 8388608ul]’:
./Main.cpp:74:13: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
             fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 5
AC × 27
WA × 34
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt
Case Name Status Exec Time Memory
0_00.txt AC 11 ms 6400 KB
0_01.txt AC 11 ms 6400 KB
0_02.txt AC 11 ms 6400 KB
0_03.txt AC 11 ms 6400 KB
0_04.txt AC 11 ms 6400 KB
1_00.txt AC 10 ms 6400 KB
1_01.txt AC 11 ms 6400 KB
1_02.txt AC 32 ms 8832 KB
1_03.txt AC 31 ms 8960 KB
1_04.txt AC 23 ms 8576 KB
1_05.txt AC 24 ms 6784 KB
1_06.txt AC 24 ms 6784 KB
1_07.txt AC 25 ms 6784 KB
1_08.txt WA 32 ms 8832 KB
1_09.txt WA 32 ms 8832 KB
1_10.txt WA 32 ms 8832 KB
1_11.txt WA 32 ms 8832 KB
1_12.txt AC 34 ms 8832 KB
1_13.txt WA 32 ms 8832 KB
1_14.txt WA 31 ms 8832 KB
1_15.txt AC 35 ms 8832 KB
1_16.txt AC 54 ms 9088 KB
1_17.txt AC 54 ms 9088 KB
1_18.txt WA 36 ms 8832 KB
1_19.txt WA 36 ms 8832 KB
1_20.txt AC 53 ms 9088 KB
1_21.txt WA 36 ms 8832 KB
1_22.txt WA 36 ms 8832 KB
1_23.txt WA 36 ms 8832 KB
1_24.txt AC 13 ms 8448 KB
1_25.txt AC 13 ms 8448 KB
1_26.txt AC 13 ms 8448 KB
1_27.txt AC 13 ms 8448 KB
1_28.txt AC 16 ms 8704 KB
1_29.txt AC 13 ms 8448 KB
1_30.txt AC 14 ms 8448 KB
1_31.txt AC 17 ms 8704 KB
1_32.txt WA 16 ms 8576 KB
1_33.txt WA 18 ms 8704 KB
1_34.txt WA 18 ms 8704 KB
1_35.txt WA 22 ms 8832 KB
1_36.txt WA 16 ms 8576 KB
1_37.txt WA 19 ms 8704 KB
1_38.txt WA 16 ms 8704 KB
1_39.txt WA 15 ms 8576 KB
1_40.txt WA 18 ms 8704 KB
1_41.txt WA 20 ms 8832 KB
1_42.txt WA 19 ms 8832 KB
1_43.txt WA 19 ms 8704 KB
1_44.txt WA 23 ms 8832 KB
1_45.txt WA 23 ms 8832 KB
1_46.txt WA 23 ms 8832 KB
1_47.txt WA 23 ms 8832 KB
1_48.txt AC 45 ms 9600 KB
1_49.txt WA 25 ms 8832 KB
1_50.txt WA 25 ms 8832 KB
1_51.txt WA 26 ms 8832 KB
1_52.txt WA 29 ms 8832 KB
1_53.txt WA 30 ms 8832 KB
1_54.txt WA 29 ms 8832 KB
1_55.txt WA 29 ms 8832 KB