Submission #348527

#TimeUsernameProblemLanguageResultExecution timeMemory
348527arnold518Queue (CEOI06_queue)C++14
8 / 100
124 ms65540 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 5e4; const int INF = 1e9+100; const int MOD = 250007; int N, Q; pii A[MOD]; int B[MOD]; int getA(int x) { if(A[x].first==-1) return x-1; return A[x].first; } int getB(int x) { if(A[x].second==-1) return x+1; return A[x].second; } int main() { scanf("%d", &N); for(int i=0; i<MOD; i++) A[i]=pii(-1, -1), B[i]=-1; for(int i=1; i<=N; i++) { int a, b; scanf("%d%d", &a, &b); int p=getA(a), q=getB(a), r=getA(b); swap(b, r); A[p%MOD].second=q; A[q%MOD].first=p; A[a%MOD].first=b; A[a%MOD].second=r; A[b%MOD].second=a; A[r%MOD].first=a; B[p%MOD]=p; B[q%MOD]=q; B[a%MOD]=a; B[a%MOD]=a; B[b%MOD]=b; B[r%MOD]=r; } vector<pii> V; vector<pii> BB; vector<int> V2; vector<pii> C; V.push_back({-1, -1}); V2.push_back(0); for(int i=0; i<MOD; i++) { if(B[i]!=-1) BB.push_back(pii(B[i], A[i].second)); } sort(BB.begin(), BB.end()); int now=0; while(1) { auto it=lower_bound(BB.begin(), BB.end(), pii(now, 0)); if(it!=BB.end() && it->first==now) { C.push_back({now, V.size()}); V.push_back({now, now}); V2.push_back(V2.back()+1); now=it->second; } else { if(it==BB.end()) { C.push_back({INF, V.size()}); V.push_back({now, INF}); V2.push_back(V2.back()+INF-now+1); break; } else { C.push_back({it->first-1, V.size()}); V.push_back({now, it->first-1}); V2.push_back(V2.back()+it->first-now); now=it->first; } } } /* for(int i=0; i<V.size(); i++) { printf("%d %d : %d\n", V[i].first, V[i].second, V2[i]); } */ sort(C.begin(), C.end()); scanf("%d", &Q); for(int i=1; i<=Q; i++) { char c; int x; scanf(" %c%d", &c, &x); if(c=='P') { int it=lower_bound(C.begin(), C.end(), pii(x, -2))->second; int ans=V2[it-1]+x-V[it].first; printf("%d\n", ans); } else { x++; int it=lower_bound(V2.begin(), V2.end(), x)-V2.begin(); int ans=V[it].first+x-V2[it-1]-1; printf("%d\n", ans); } } }

Compilation message (stderr)

queue.cpp: In function 'int main()':
queue.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
queue.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   scanf(" %c%d", &c, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...