Submission #1163723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163723		emptypringlescan	Specijacija (COCI20_specijacija)	C++20	20 / 110	4101 ms	358400 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int buc=450;
long long arr[200005],lvl[200005],bruh[200005];

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q,t;
    cin >> n >> q >> t;
    int seg[n/buc+5][buc+buc+5],snap[n/buc+5][n+5],sz[n/buc+5];
    memset(sz,0,sizeof(sz));
    for(int i=0; i<n; i++){
		cin >> arr[i];
		lvl[i]=arr[i]-(long long)i*(i+1)/2ll;
		bruh[i]=(long long)i*(i+1)/2ll;
	}
	bruh[n]=(long long)n*(n+1)/2ll;
	for(int i=0; i<n/buc; i++){
		int st=i*buc,en=min((i+1)*buc-1,n-1);
		int cur=0;
		for(int j=1; j<=st+1; j++){
			seg[cur][sz[cur]]=j;
			sz[cur]++;
			if(sz[cur]>=buc) cur++;
		}
		for(int j=st; j<=en; j++){
			int x=lvl[j];
			cur=0;
			while(sz[cur]<x){
				x-=sz[cur];
				cur++;
			}
			int yay=seg[cur][x-1];
			seg[cur][sz[cur]]=yay;
			sz[cur]++;
			for(int k=sz[cur]-2; k>=0; k--){
				if(seg[cur][k]==yay) break;
				swap(seg[cur][k],seg[cur][k+1]);
			}
		}
		cur=0;
		for(int j=0; j<=n/buc+3; j++){
			for(int k=0; k<sz[j]; k++){
				snap[i][cur]=seg[j][k];
				cur++;
				seg[j][k]=0;
			}
			sz[j]=0;
		}
	}
	
	long long prevans=0;
	const long long mod=(long long)(n+1)*(n+2)/2ll;
	while(q--){
		long long xx,yy;
		cin >> xx >> yy;
		long long x=(xx-1+t*prevans)%mod+1;
		long long y=(yy-1+t*prevans)%mod+1;
		if(x<y) swap(x,y);
		int depx=lower_bound(bruh,bruh+n+1,x)-bruh-1;
		int depy=lower_bound(bruh,bruh+n+1,y)-bruh-1;
		int lx=x-bruh[depx];
		int ly=y-bruh[depy];
		while(depx>depy){
			if(depx-buc>=depy&&depx%buc==0){
				lx=snap[depx/buc-1][lx-1];
				depx-=buc;
			}
			else{
				lx-=(lvl[depx-1]<lx);
				depx--;
			}
		}
		//cout << lx << ' ' << depx << ' ' << ly << ' ' << depy << '\n';
		if(lx==ly){
			prevans=bruh[depx]+lx;
			cout << bruh[depx]+lx << '\n';
			continue;
		}
		while(lx!=ly){
			//cout << lx << ' ' << ly << '\n';
			int nx,ny;
			if(depx%buc==0){
				int hm=depx/buc-1;
				nx=snap[hm][lx-1];
				ny=snap[hm][ly-1];
				if(nx!=ny){
					depx-=buc;
					lx=nx; ly=ny;
					continue;
				}
			}
			lx-=(lvl[depx-1]<lx);
			ly-=(lvl[depx-1]<ly);
			depx--;
		}
		prevans=bruh[depx]+lx;
		cout << bruh[depx]+lx << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60