Submission #152430

#TimeUsernameProblemLanguageResultExecution timeMemory
152430arnold518Sushi (JOI16_sushi)C++14
100 / 100
11266 ms145480 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 = 400000; const int MAXQ = 25000; int N, Q, A[MAXN+10], SQ; priority_queue<int> PQ1[MAXN+10]; priority_queue<int, vector<int>, greater<int>> PQ2[MAXN+10]; int solve(int S, int T, int P) { int i, j; if(S/SQ==T/SQ) { int l=max(1, S/SQ*SQ), r=min(N, S/SQ*SQ+SQ-1); for(i=l; i<=r; i++) { PQ2[S/SQ].push(A[i]); A[i]=PQ2[S/SQ].top(); PQ2[S/SQ].pop(); } while(!PQ2[S/SQ].empty()) PQ2[S/SQ].pop(); while(!PQ1[S/SQ].empty()) PQ1[S/SQ].pop(); for(i=S; i<=T; i++) if(P<A[i]) swap(A[i], P); for(i=l; i<=r; i++) PQ1[S/SQ].push(A[i]); } else { int l, r; l=max(1, S/SQ*SQ), r=min(N, S/SQ*SQ+SQ-1); for(i=l; i<=r; i++) { PQ2[S/SQ].push(A[i]); A[i]=PQ2[S/SQ].top(); PQ2[S/SQ].pop(); } while(!PQ2[S/SQ].empty()) PQ2[S/SQ].pop(); while(!PQ1[S/SQ].empty()) PQ1[S/SQ].pop(); for(i=S; i<=r; i++) if(P<A[i]) swap(A[i], P); for(i=l; i<=r; i++) PQ1[S/SQ].push(A[i]); for(i=S/SQ+1; i<T/SQ; i++) { PQ1[i].push(P); PQ2[i].push(P); P=PQ1[i].top(); PQ1[i].pop(); } l=max(1, T/SQ*SQ), r=min(N, T/SQ*SQ+SQ-1); for(i=l; i<=r; i++) { PQ2[T/SQ].push(A[i]); A[i]=PQ2[T/SQ].top(); PQ2[T/SQ].pop(); } while(!PQ2[T/SQ].empty()) PQ2[T/SQ].pop(); while(!PQ1[T/SQ].empty()) PQ1[T/SQ].pop(); for(i=l; i<=T; i++) if(P<A[i]) swap(A[i], P); for(i=l; i<=r; i++) PQ1[T/SQ].push(A[i]); } return P; } int main() { int i, j; scanf("%d%d", &N, &Q); SQ=400; priority_queue<int> PQ; for(i=1; i<=N; i++) { scanf("%d", &A[i]); PQ1[i/SQ].push(A[i]); } while(Q--) { int S, T, P; scanf("%d%d%d", &S, &T, &P); if(S<=T) printf("%d\n", solve(S, T, P)); else { P=solve(S, N, P); printf("%d\n", solve(1, T, P)); } /* for(i=0; i<=N/SQ; i++) { printf("bucket : %d\n", i); vector<int> V; printf("PQ1 : "); while(!PQ1[i].empty()) printf("%d ", PQ1[i].top()), V.push_back(PQ1[i].top()), PQ1[i].pop(); printf("\n"); while(!V.empty()) PQ1[i].push(V.back()), V.pop_back(); printf("PQ2 : "); while(!PQ2[i].empty()) printf("%d ", PQ2[i].top()), V.push_back(PQ2[i].top()), PQ2[i].pop(); printf("\n"); while(!V.empty()) PQ2[i].push(V.back()), V.pop_back(); } for(i=1; i<=N; i++) printf("%d ", A[i]); printf("\n"); printf("============\n"); */ } }

Compilation message (stderr)

sushi.cpp: In function 'int solve(int, int, int)':
sushi.cpp:17:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sushi.cpp: In function 'int main()':
sushi.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sushi.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
sushi.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &S, &T, &P);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...