Submission #368057

#	Time	Username	Problem	Language	Result	Execution time	Memory
368057		arnold518	Specijacija (COCI20_specijacija)	C++14	0 / 110	1130 ms	312548 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

int N, Q, T;
ll A[MAXN+10];

struct BIT
{
	int tree[MAXN+10];
	void update(int i, int k)
	{
		for(; i<=N+1; i+=(i&-i))
		{
			tree[i]+=k;
		}
	}
	int query(int i)
	{
		int ret=0;
		for(; i>0; i-=(i&-i))
		{
			ret+=tree[i];
		}
		return ret;
	}
}bit;

int B[MAXN+10];
int par[MAXN+10], spa[MAXN+10][30], dep[MAXN+10];
int L[MAXN+10], R[MAXN+10];

struct SEG
{
	vector<pii> tree[MAXN*4+10];
	void update(int node, int tl, int tr, int l, int r, pii k)
	{
		if(l<=tl && tr<=r)
		{
			tree[node].push_back(k);
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}
	void init(int node, int tl, int tr)
	{
		sort(tree[node].begin(), tree[node].end());
		if(tl==tr) return;
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
	}
	int query(int node, int tl, int tr, int p, int k)
	{
		int val=lower_bound(tree[node].begin(), tree[node].end(), pii(k, 987654321))-tree[node].begin();
		if(tl==tr) return val;
		int mid=tl+tr>>1;
		if(p<=mid) return query(node*2, tl, mid, p, k)+val;
		else return query(node*2+1, mid+1, tr, p, k)+val;
	}
	int query2(int node, int tl, int tr, int p, int k)
	{
		auto it=lower_bound(tree[node].begin(), tree[node].end(), pii(k, 987654321));
		if(it!=tree[node].begin())
		{
			it--;
			if(it->first==k) return it->second;
		}
		if(tl==tr) assert(0);
		int mid=tl+tr>>1;
		if(p<=mid) return query2(node*2, tl, mid, p, k);
		else return query2(node*2+1, mid+1, tr, p, k);
	}
}seg;

int level(ll x)
{
	int lo=1, hi=N+2;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if((ll)mid*(mid-1)/2<x) lo=mid;
		else hi=mid;
	}
	return lo;
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[spa[v][i]]>=dep[u]) v=spa[v][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(spa[u][i]!=spa[v][i]) u=spa[u][i], v=spa[v][i];
	return spa[u][0];
}

int getv(ll x)
{
	if(x==1) return N+1;
	int l=level(x);
	int p=x-(ll)l*(l-1)/2;
	int lo=0, hi=N+1;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		//printf("?? %d %d -> %d\n", l, mid, seg.query(1, 1, N+1, l, mid));
		if(seg.query(1, 1, N+1, l, mid)>=p) hi=mid;
		else lo=mid;
	}
	//printf("!! %d %d\n", l, hi);
	int val=seg.query2(1, 1, N+1, l, hi);
	//printf("GETV %lld %d\n", x, val);
	return val;
}

int main()
{
	scanf("%d%d%d", &N, &Q, &T);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);

	for(int i=1; i<=N+1; i++) bit.update(i, 1);
	for(int i=1; i<=N+1; i++)
	{
		B[i]=i, L[i]=R[i]=i;
		dep[i]=N+1;
	}
	for(int i=N; i>=1; i--)
	{
		int p=A[i]-(ll)i*(i-1)/2;
		int l, r;
		int lo=0, hi=N+1;
		while(lo+1<hi)
		{	
			int mid=lo+hi>>1;
			if(bit.query(mid)<p) lo=mid;
			else hi=mid;
		}
		l=hi;

		lo=0, hi=N+1;
		while(lo+1<hi)
		{	
			int mid=lo+hi>>1;
			if(bit.query(mid)<p+1) lo=mid;
			else hi=mid;
		}
		r=hi;

		par[B[l]]=i+N+1;
		par[B[r]]=i+N+1;
		spa[B[l]][0]=i+N+1;
		spa[B[r]][0]=i+N+1;
		dep[i+N+1]=i;
		L[i+N+1]=L[B[l]];
		R[i+N+1]=R[B[r]];
		bit.update(r, -1);
		B[r]=0; B[l]=i+N+1;
	}

	//for(int i=1; i<=N+N+1; i++) printf("%d : %d\n", i, L[i]);
	for(int i=1; i<=N+1; i++)
	{
		int l=par[i]-N, r=N+1;
		//printf("%d : %d %d\n", i, l, r);
		seg.update(1, 1, N+1, l, r, pii(L[i], i));
	}
	for(int i=N+3; i<=N+N+1; i++)
	{
		int l=par[i]-N, r=i-N-1;
		//printf("%d : %d %d\n", i, l, r);
		seg.update(1, 1, N+1, l, r, pii(L[i], i));	
	}
	seg.update(1, 1, N+1, 1, 1, pii(1, N+2));

	spa[N+2][0]=N+2;
	for(int i=1; i<=20; i++) for(int j=1; j<=N+N+1; j++) spa[j][i]=spa[spa[j][i-1]][i-1];

	seg.init(1, 1, N+1);
	//for(int i=1; i<=N+1; i++) if(seg.query(1, 1, N+1, i, 987654321)!=i) while(1);

	assert(0);

	ll bef=0;
	while(Q--)
	{
		ll u, v;
		scanf("%lld%lld", &u, &v);
		u=(((u-1+T*bef)%((ll)(N+1)*(N+2)/2)))+1;
		v=(((v-1+T*bef)%((ll)(N+1)*(N+2)/2)))+1;
		//printf("%lld %lld\n", u, v);
		int lu, lv;
		lu=getv(u); lv=getv(v);
		//printf("!%d %d\n", lu, lv);
		if(lu==lv) printf("%lld\n", bef=min(u, v));
		else if(L[lu]<=L[lv] && R[lv]<=R[lu]) printf("%lld\n", bef=u);
		else if(L[lv]<=L[lu] && R[lu]<=R[lv]) printf("%lld\n", bef=v);
		else
		{
			int w=lca(lu, lv);
			//printf("WOW %d\n", w);
			printf("%lld\n", bef=A[w-N-1]);
		}
	}
}

Compilation message (stderr)

Main.cpp: In member function 'void SEG::update(int, int, int, int, int, pii)':
Main.cpp:49:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG::init(int, int, int)':
Main.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'int SEG::query(int, int, int, int, int)':
Main.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'int SEG::query2(int, int, int, int, int)':
Main.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'int level(ll)':
Main.cpp:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   int mid=lo+hi>>1;
      |           ~~^~~
Main.cpp: In function 'int getv(ll)':
Main.cpp:113:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |   int mid=lo+hi>>1;
      |           ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:142:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |    int mid=lo+hi>>1;
      |            ~~^~~
Main.cpp:151:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |    int mid=lo+hi>>1;
      |            ~~^~~
Main.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |  scanf("%d%d%d", &N, &Q, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:127:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
Main.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  195 |   scanf("%lld%lld", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

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