Submission #3433902
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].x=*lower_bound(b+1,b+1+m,a[i])-a[i]; p[cnt].y=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;}); 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 | 4418 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 |
|
|
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 | WA | 11 ms | 6400 KB |
1_00.txt | AC | 11 ms | 6400 KB |
1_01.txt | AC | 11 ms | 6400 KB |
1_02.txt | WA | 33 ms | 8832 KB |
1_03.txt | AC | 23 ms | 8576 KB |
1_04.txt | AC | 30 ms | 8960 KB |
1_05.txt | AC | 24 ms | 6784 KB |
1_06.txt | AC | 24 ms | 6784 KB |
1_07.txt | AC | 24 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 | 33 ms | 8832 KB |
1_12.txt | WA | 36 ms | 8832 KB |
1_13.txt | WA | 32 ms | 8832 KB |
1_14.txt | WA | 32 ms | 8832 KB |
1_15.txt | WA | 37 ms | 8832 KB |
1_16.txt | WA | 54 ms | 9088 KB |
1_17.txt | WA | 54 ms | 9088 KB |
1_18.txt | WA | 36 ms | 8832 KB |
1_19.txt | WA | 36 ms | 8832 KB |
1_20.txt | WA | 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 | 13 ms | 8448 KB |
1_31.txt | AC | 17 ms | 8704 KB |
1_32.txt | WA | 15 ms | 8576 KB |
1_33.txt | WA | 18 ms | 8704 KB |
1_34.txt | WA | 18 ms | 8704 KB |
1_35.txt | WA | 18 ms | 8832 KB |
1_36.txt | WA | 15 ms | 8576 KB |
1_37.txt | WA | 17 ms | 8704 KB |
1_38.txt | WA | 18 ms | 8704 KB |
1_39.txt | WA | 16 ms | 8576 KB |
1_40.txt | WA | 19 ms | 8704 KB |
1_41.txt | WA | 20 ms | 8832 KB |
1_42.txt | WA | 20 ms | 8832 KB |
1_43.txt | WA | 20 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 | 44 ms | 9600 KB |
1_49.txt | WA | 26 ms | 8832 KB |
1_50.txt | WA | 25 ms | 8832 KB |
1_51.txt | WA | 25 ms | 8832 KB |
1_52.txt | WA | 29 ms | 8832 KB |
1_53.txt | WA | 29 ms | 8832 KB |
1_54.txt | WA | 30 ms | 8832 KB |
1_55.txt | WA | 29 ms | 8832 KB |