제출 #605514

#제출 시각아이디문제언어결과실행 시간메모리
605514dualityEvent Hopping (BOI22_events)C++17
0 / 100
816 ms20660 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int S[100000],E[100000]; vi all; vpii qq[100000]; int order[100000],ans[100000]; int parent[200000],out[200000],outnum[200000],mm[200000]; int B; int rebuild(int b) { int i; if (mm[b] == 1e9) { for (i = b*B; i < min((b+1)*B,(int) all.size()); i++) { if (parent[i] >= i) out[i] = 1e9; else if (parent[i] < b*B) out[i] = parent[i],outnum[i] = 1; else out[i] = out[parent[i]],outnum[i] = outnum[parent[i]]+1; } } return 0; } int main() { int i; int N,Q,s,e; scanf("%d %d",&N,&Q); for (i = 0; i < N; i++) scanf("%d %d",&S[i],&E[i]),all.pb(S[i]),all.pb(E[i]); for (i = 0; i < Q; i++) { scanf("%d %d",&s,&e),s--,e--; qq[e].pb(mp(s,i)); } sort(all.begin(),all.end()); all.resize(unique(all.begin(),all.end())-all.begin()); for (i = 0; i < N; i++) { S[i] = lower_bound(all.begin(),all.end(),S[i])-all.begin(); E[i] = lower_bound(all.begin(),all.end(),E[i])-all.begin(); order[i] = i; } sort(order,order+N,[&](int a,int b) { return E[a] < E[b]; }); int j,k; B = sqrt(all.size()); for (i = 0; i < all.size(); i++) parent[i] = mm[i] = out[i] = 1e9; for (i = 0; i < N; i++) { int u = order[i]; if (S[u]/B == E[u]/B) { for (j = S[u]; j <= E[u]; j++) parent[j] = min(parent[j],S[u]); rebuild(S[u]/B); } else { for (j = S[u]; j < (S[u]/B+1)*B; j++) parent[j] = min(parent[j],S[u]); for (j = S[u]/B+1; j < E[u]/B; j++) { if (j == S[u]/B+1) { for (k = j*B; k < (j+1)*B; k++) parent[k] = min(parent[k],S[u]); rebuild(j); } else mm[j] = min(mm[j],S[u]); } for (j = (E[u]/B)*B; j <= E[u]; j++) parent[j] = min(parent[j],S[u]); rebuild(S[u]/B),rebuild(E[u]/B); } for (auto [s,j]: qq[u]) { if (s == u) ans[j] = 0; else if (E[s] > E[u]) ans[j] = -1; else { int v = S[u]; ans[j] = 1; while (v > E[s]) { if ((v-E[s] < 2*B+5) || (mm[v/B] != 1e9)) { if (min(mm[v/B],parent[v]) >= v) { ans[j] = -1; break; } else v = min(mm[v/B],parent[v]),ans[j]++; } else ans[j] += outnum[v],v = out[v]; } } } } for (i = 0; i < Q; i++) { if (ans[i] == -1) printf("impossible\n"); else printf("%d\n",ans[i]); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

events.cpp: In function 'int main()':
events.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (i = 0; i < all.size(); i++) parent[i] = mm[i] = out[i] = 1e9;
      |                 ~~^~~~~~~~~~~~
events.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~
events.cpp:79:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     for (i = 0; i < N; i++) scanf("%d %d",&S[i],&E[i]),all.pb(S[i]),all.pb(E[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
events.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d %d",&s,&e),s--,e--;
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...