Submission #1260927

#TimeUsernameProblemLanguageResultExecution timeMemory
1260927raymoo_Index (COCI21_index)C++17
60 / 110
2591 ms8264 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define eb emplace_back #define umap unordered_map #define prq priority_queue #define vect vector #define rs resize #define bend(v) v.begin(),v.end() #define pob pop_back #define pof pop_front #define lwb lower_bound #define upb upper_bound #define pii pair<int,int> #define nextl cout << '\n' #define el '\n' #define deb cout<<"\nok\n";return #define ll long long #define dbl long double #define popcnt __builtin_popcount #define ctz __builtin_ctz #define FILE "ellencute" const ll INF=902337203695775807, N=2e5+69, MOD=1e9+7; void ffopen(){ if(fopen(FILE".inp", "r")){ freopen(FILE".inp", "r", stdin); freopen(FILE".out", "w", stdout); }else if(fopen("ellencute.inp", "r")){ freopen("ellencute.inp", "r", stdin); freopen("ellencute.out", "w", stdout); } } int pm(int a,const int b=1e9+7){return ((a%b)+b)%b;} int sq(int x){return x*x;} ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){ if(a == -1 || b == -1)return -1; ll g = __gcd(a,b); if(b/g > lim/a)return -1; return (a/g)*b; } int t[4*N], lz[4*N]; struct Seggs{ Seggs(){build();} void build(int l=1, int r=2e5, int id=1){ if(l == r){ t[id] = -l; return; } int mid = (l+r)/2; build(l, mid, id*2); build(mid+1, r, id*2+1); t[id] = max(t[id*2], t[id*2+1]); } void push(int l, int r, int id, bool b=0){ t[id] += lz[id]; if(l < r){ lz[id*2] += lz[id]; lz[id*2+1] += lz[id]; if(b){ int mid = (l+r)/2; push(l, mid, id*2); push(mid+1, r, id*2+1); t[id] = max(t[id*2], t[id*2+1]); } } lz[id] = 0; } void upd(int p, int x, int l=1, int r=2e5, int id=1){ push(l, r, id); if(l > p)return; if(r <= p){ lz[id]+=x; push(l, r, id); return; } int mid = (l+r)/2; upd(p, x, l, mid, id*2); upd(p, x, mid+1, r, id*2+1); t[id] = max(t[id*2], t[id*2+1]); } int get(int l=1, int r=2e5, int id=1){ push(l, r, id, 1); if(l == r)return l; int mid = (l+r)/2; if(t[id*2+1]>=0)return get(mid+1, r, id*2+1); return get(l, mid, id*2); } } sgt; struct query{ int l, r, id; }; void sol(){ int n, q; cin >> n >> q; int a[n], ans[q]; for(int& i : a)cin >> i; query que[q]; for(int i=0;q>i;i++){ cin >> que[i].l >> que[i].r; que[i].l--;que[i].r--; que[i].id=i; } const int S = 2*sqrt(n / log2(n)); sort(que, que+q, [&](const query& a, const query& b){ if(a.l/S != b.l/S)return a.l < b.l; if(a.l/S & 1)return a.r < b.r; return a.r > b.r; }); int l=0, r=-1; for(auto [L, R, id] : que){ while(r<R)sgt.upd(a[++r], 1); while(l>L)sgt.upd(a[--l], 1); while(r>R)sgt.upd(a[r--], -1); while(l<L)sgt.upd(a[l++], -1); ans[id] = sgt.get(); } for(int i : ans)cout << i << el; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ffopen(); int t=1; //cin >> t; while(t--)sol(); } /* ...-%%%%%%%%%%%... .:**#%=%%%%%+........-%%%%. . .%%%%%%=-..%#. .#%%. %%%+.. .: *%%. .%%. :. :%%%%%:. .%%. ... .: :: .=%%%. ..%%. #%#:%. : :.. =%%. %%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%.. .%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%. .%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%. =%%%...-%%%:::*%********%:::%%%****%::::::::%% .%- .%::::%%***%=:%%**********%%********%:::::::=%-:. .%.. #%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%. .%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%. .%%#%+%%***************##*+=+*==********************%%.:. .%% .%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%. .#%#*********************%%**************++************%%::::::%* .%%%. .%%***************#*****%%%****************************%%::::::%% .-%%%. .#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%. .%%**************#**%%%----%********%%**************#***#%%%#**%#******%* .%%**************#%%%--.....%%*******%%**************#**********#%******%%. .%%*************%%...........%%******%-%*************#***********%%*****%%. .%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%# .%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%% .#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%. .%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%. .+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%- ..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%. .%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%. .%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%. .%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%. ..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%. .%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%. ..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%.. -%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%. .%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%. .%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%. .+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%: =%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%% .%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%% *%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%% .%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%* %%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%. %%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%. .%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%.. :%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% . *%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*.. .%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . ..... %%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%. ..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%# .-%%+. ... .%%%%%%%:. */

Compilation message (stderr)

index.cpp: In function 'void ffopen()':
index.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(FILE".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(FILE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("ellencute.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("ellencute.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...