oj.uz

Submission #807582

# Submission time Handle Problem Language Result Execution time Memory
807582 2023-08-04T19:44:23 Z I_Love_EliskaM_ Comparing Plants (IOI20_plants) C++17
5 / 100
 80 ms 14880 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,_n) for(int i=0;i<_n;++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

const int N=2e5+55;
int p[N], L[N], R[N];
int n;
int k;

struct sgt {
	vector<int> t,lazy; int sz=1;
	sgt(int n) {
		while (sz<n) sz<<=1;
		t.assign(2*sz,0);
		lazy.assign(4*sz,0);
	}
	void push(int v) {
		t[v]+=lazy[v];
		lazy[2*v+1]+=lazy[v];
		lazy[2*v+2]+=lazy[v];
		lazy[v]=0;
	}
	void add(int v, int l, int r, int lx, int rx, int x) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			lazy[v]+=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		add(2*v+1,l,m,lx,rx,x);
		add(2*v+2,m,r,lx,rx,x);
		t[v]=max(t[2*v+1],t[2*v+2]);
	}
	void add(int l, int r, int x) {
		add(0,0,sz,l,r,x);
	}
	int query(int v, int l, int r, int lx, int rx) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return -1e9-7;
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		int lq=query(2*v+1,l,m,lx,rx);
		int rq=query(2*v+2,m,r,lx,rx);
		t[v]=max(t[2*v+1],t[2*v+2]);
		return max(lq,rq);
	}
	int query(int l, int r) {
		return query(0,0,sz,l,r);
	}
};
sgt st(N);

vector<int> adj[305];
int vis[305];
bitset<305> bs[305];

void dfs(int u) {
	if (vis[u]==1) assert(0);
	if (vis[u]) return;
	bs[u][u]=1;
	vis[u]=1;
	for(auto&v:adj[u]) {
		dfs(v);
		bs[u]|=bs[v];
	}
	vis[u]=2;
}

void init(int _k, vector<int> r) {
	k=_k;
	n=r.size();

	if (n<=300) {
		forn(i,n) r[i]=k-1-r[i];
		forn(i,n) r.pb(r[i]);
		forn(i,n) {
			vector<pi> v;
			for (int j=i+1; j<i+k; ++j) v.pb({r[j],j});
			sort(all(v));
			forn(j,k-1) {
				if (j<r[i]) adj[i].pb(v[j].s%n);
				else adj[v[j].s%n].pb(i);
			}
		}
		forn(i,n) {
			if (vis[i]) continue;
			dfs(i);
		}
		forn(i,n) r[i]=k-1-r[i];
	}

	if (k==2) {
		int z=0;
		forn(i,n) r[i]^=1;
		forn(i,n) if (r[i]==0) z=i;
		for (int i=z+n; i>z; --i) {
			if (r[i%n]) R[i%n]=R[(i+1)%n];
			else R[i%n]=i%n;
		}
		z=0;
		forn(i,n) if (r[i]) z=i;
		++z;
		for (int i=z; i<z+n; ++i) {
			if (r[(i-1+n)%n]) L[i%n]=i%n;
			else L[i%n]=L[(i-1+n)%n];
		}
		forn(i,n) {
			L[i]+=n, R[i]+=n;
		}
		forn(i,n) {
			if (L[i]==R[i] && L[i]==i+n) continue;
			if (L[i]>=R[i]) L[i]-=n;
		}
		return;
	}

	if (2*k>n) {
		forn(i,n) st.add(i,i+1,r[i]);

		forn(i,n) {
			int l=0, r=n-1;
			while (l<r) {
				int mid=(l+r+1)>>1;
				int x=st.query(mid,n);
				if (x!=k-1) r=mid-1;
				else l=mid;
			}
			int z=r;

			l=0, r=k;
			while (l<r) {
				int mid=(l+r)>>1;
				int f=z-k+1;
				int x;
				if (f>=0) {
					x=st.query(f,f+mid+1);
				} else {
					if (f+mid+1>0) {
						x=max(st.query(f+n,n),st.query(0,f+mid+1));
					} else {
						x=st.query(f+n,f+mid+1+n);
					}
				}
				if (x==k-1) r=mid;
				else l=mid+1;
			}
			z=z-k+1+r;
			if (z<0) z+=n;
			p[z]=i;
			st.add(z,z+1,-k);

			int f=z-k+1;
			if (f>=0) {
				st.add(f,z,1);
			} else {
				st.add(0,z,1);
				st.add(n+f,n,1);
			}
		}
		return;
	}
	//vector<int> pr(2*n+1,0);
	//forn(i,2*n) pr[i+1]=pr[i]+(r[i]==0);

}

int compare_plants(int x, int y) {
	if (k==2) {
		if (L[x]<=y && y<=R[x]) return 1;
		if (L[x]<=y+n && y+n<=R[x]) return 1;
		swap(x,y);
		if (L[x]<=y && y<=R[x]) return -1;
		if (L[x]<=y+n && y+n<=R[x]) return -1;
		return 0;
	}
	if (2*k>n) {
		if (p[x]>p[y]) return 1;
		else return -1;
	}
	if (bs[x][y]) {
		return 1;
	}
	if (bs[y][x]) {
		return -1;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 42 ms 10260 KB Output is correct
7 Correct 48 ms 11720 KB Output is correct
8 Correct 63 ms 14860 KB Output is correct
9 Correct 63 ms 14860 KB Output is correct
10 Correct 65 ms 14848 KB Output is correct
11 Correct 80 ms 14848 KB Output is correct
12 Correct 65 ms 14820 KB Output is correct
13 Correct 61 ms 14828 KB Output is correct
14 Correct 78 ms 14880 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Runtime error 11 ms 13108 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Runtime error 11 ms 13108 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Runtime error 9 ms 12884 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 4 ms 6452 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Runtime error 14 ms 13128 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Runtime error 9 ms 12900 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 42 ms 10260 KB Output is correct
7 Correct 48 ms 11720 KB Output is correct
8 Correct 63 ms 14860 KB Output is correct
9 Correct 63 ms 14860 KB Output is correct
10 Correct 65 ms 14848 KB Output is correct
11 Correct 80 ms 14848 KB Output is correct
12 Correct 65 ms 14820 KB Output is correct
13 Correct 61 ms 14828 KB Output is correct
14 Correct 78 ms 14880 KB Output is correct
15 Correct 3 ms 6492 KB Output is correct
16 Correct 3 ms 6484 KB Output is correct
17 Correct 3 ms 6492 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Runtime error 11 ms 13108 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -