Submission #1163560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163560		emptypringlescan	Specijacija (COCI20_specijacija)	C++20	20 / 110	4103 ms	357776 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long buc=450;
long long arr[200005],lvl[200005],bruh[200005];
vector<int> seg[450+5],snap[450+5];
int inc1(int d, int l){
	assert(d>0);
	if(lvl[d-1]<l) return l-1;
	else return l;
}
int incbuc(int d, int l){
	assert(d%buc==0);
	int b=d/buc-1;
	if(b<0) exit(0);
	return snap[b][l-1];
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q,t;
    cin >> n >> q >> t;
    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,(long long)n-1);
		int cur=0;
		for(int j=1; j<=st+1; j++){
			seg[cur].push_back(j);
			if((int)seg[cur].size()>=buc) cur++;
		}
		for(int j=st; j<=en; j++){
			int x=lvl[j];
			cur=0;
			while((int)seg[cur].size()<x){
				x-=seg[cur].size();
				cur++;
			}
			int yay=seg[cur][x-1];
			seg[cur].push_back(yay);
			for(int k=(int)seg[cur].size()-2; k>=0; k--){
				if(seg[cur][k]==yay) break;
				swap(seg[cur][k],seg[cur][k+1]);
			}
		}
		for(int j=0; j<=buc; j++){
			for(int k:seg[j]){
				snap[i].push_back(k);
			}
			seg[j].clear();
		}
	}
	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=incbuc(depx,lx);
				depx-=buc;
			}
			else{
				lx=inc1(depx,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){
				nx=incbuc(depx,lx);
				ny=incbuc(depy,ly);
				if(nx!=ny){
					depx-=buc; depy-=buc;
					lx=nx; ly=ny;
					continue;
				}
			}
			lx=inc1(depx,lx);
			ly=inc1(depy,ly);
			depx--; depy--;
		}
		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