Submission #199444

#TimeUsernameProblemLanguageResultExecution timeMemory
199444dennisstarSushi (JOI16_sushi)C++17
0 / 100
12094 ms26040 KiB
#include <bits/stdc++.h> #define fi first #define se second #define em emplace #define eb emplace_back #define all(V) (V).begin(), (V).end() using namespace std; typedef vector<int> vim; typedef pair<int, int> pii; const int sz = 500; int N, M, Q, X[400010], chk[400010]; vector<pii> B[810]; multiset<int> S[810]; inline void make(int t) { B[t].clear(); S[t].clear(); int ub=min((t+1)*sz, N); for (int i=t*sz; i<ub; i++) B[t].eb(X[i], i), chk[i]=1; sort(all(B[t])); for (auto &i:B[t]) S[t].em(i.fi); } inline void upd(int t) { auto it=S[t].begin(); for (auto &i:B[t]) { i.fi=(*it); X[i.se]=i.fi; ++it; } } inline int solve(int t, int p) { if (!(0<=t&&t<M)) exit(0); S[t].em(p); p=(*prev(S[t].end())); S[t].erase(prev(S[t].end())); return p; } int main() { scanf("%d %d", &N, &Q); M=(N+sz-1)/sz; for (int i=0; i<N; i++) scanf("%d", &X[i]); for (int i=0; i<M; i++) make(i); while (Q--) { int s, t, p; scanf("%d %d %d", &s, &t, &p); s--; t--; int sb=s/sz, tb=t/sz; upd(sb); upd(tb); if (s<=t&&sb==tb) { for (int i=s; i<=t; i++) if (X[i]>p) swap(X[i], p); make(sb); printf("%d\n", p); continue; } int ub=min((sb+1)*sz, N); for (int i=s; i<ub; i++) if (X[i]>p) swap(X[i], p); ub=s<t?tb:M; for (int i=sb+1; i<tb; i++) p=solve(i, p); if (s>t) for (int i=0; i<tb; i++) p=solve(i, p); for (int i=tb*sz; i<=t; i++) if (X[i]>p) swap(X[i], p); make(sb); make(tb); printf("%d\n", p); } return 0; }

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q); M=(N+sz-1)/sz;
  ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0; i<N; i++) scanf("%d", &X[i]);
                          ~~~~~^~~~~~~~~~~~~
sushi.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &s, &t, &p); s--; t--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...