Submission #1209492

#TimeUsernameProblemLanguageResultExecution timeMemory
1209492ricardsjansonsSecret (JOI14_secret)C++20
0 / 100
337 ms4508 KiB
#include "secret.h" #include <bits/stdc++.h> #define pf first #define sf second using namespace std; const int N=1<<10; vector<vector<pair<int,int>>>segt(N*2); void upd(int i,int x){ i+=N; segt[i]=vector<pair<int,int>>(1,{x,x}); for(i/=2;i;i/=2){ auto v1=segt[i*2]; auto v2=segt[i*2+1]; if(v1.empty()||v2.empty()){ break; } int h=v1.size(); segt[i].resize(h*2); for(int j=0;j<h*2;j++){ if(j<h){ segt[i][j].pf=v1[j].pf; }else{ segt[i][j].pf=Secret(v1.back().pf,v2[j-h].pf); } } for(int j=h*2-1;j>=0;j--){ if(j>=h){ segt[i][j].sf=v2[j-h].sf; }else{ segt[i][j].sf=Secret(v1[j].sf,v2[0].sf); } } } } void Init(int n, int a[]) { for(int i=0;i<n;i++){ upd(i,a[i]); } } int Query(int l, int r) { int lo=l,ro=r; l+=N; r+=N; if(l==r){ return segt[l][0].pf; } while(l+1<r){ l/=2;r/=2; } int h=segt[l].size(); lo%=h; ro%=h; int res=Secret(segt[l][lo].sf,segt[r][ro].pf); //cout<<l<<" "<<r<<" "<<lo<<" "<<ro<<" "<<h<<" "<<segt[l][lo].sf<<" "<<segt[r][ro].pf<<endl; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...