Submission #191491

#TimeUsernameProblemLanguageResultExecution timeMemory
191491dndhkSushi (JOI16_sushi)C++14
15 / 100
1535 ms10720 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAX_N = 400000; const int SQ = 700; int N, Q; int arr[MAX_N+1]; int g[MAX_N+1]; priority_queue<int> pq1[SQ+1], pq2; int solve(int gn, int s, int e, int k){ int x = gn*SQ+1, y = min((gn+1)*SQ, N); //cout<<s<<" "<<e<<" "<<k<<" "<<endl; //cout<<x<<" "<<y<<endl; if(s<=x && y<=e){ pq1[gn].push(k); k = pq1[gn].top(); pq1[gn].pop(); return k; }else{ while(!pq2.empty()) pq2.pop(); for(int i=y; i>=x; i--){ while(!pq1[gn].empty() && !pq2.empty() && pq1[gn].top()==pq2.top()){ pq1[gn].pop(); pq2.pop(); } //cout<<i<<" "<<pq1[gn].top()<<" "<<arr[i]<<endl; if(arr[i]>pq1[gn].top()){ arr[i] = pq1[gn].top(); pq1[gn].pop(); }else{ pq2.push(arr[i]); } } for(int i=x; i<=y; i++){ if(s<=i && i<=e){ if(k<arr[i]){ int tmp = k; k = arr[i]; arr[i] = tmp; } } pq1[gn].push(arr[i]); } return k; } } int main(){ scanf("%d%d", &N, &Q); for(int i=1; i<=N; i++){ scanf("%d", &arr[i]); g[i] = (i-1)/SQ; pq1[g[i]].push(arr[i]); } for(int i=1; i<=Q; i++){ int s, e, k; scanf("%d%d%d", &s, &e, &k); if(s<=e){ int n = g[s]; while(n<=g[e]){ k = solve(n, s, e, k); n++; } }else{ int n = g[s]; while(n<=g[N]){ k = solve(n, s, N, k); n++; } n = 0; while(n<=g[e]){ k = solve(n, 1, e, k); n++; } } printf("%d\n", k); } }

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &s, &e, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...