oj.uz

Submission #303416

# Submission time Handle Problem Language Result Execution time Memory
303416 2020-09-20T09:52:31 Z Utaha Comparing Plants (IOI20_plants) C++14
11 / 100
 65 ms 7416 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 305;
#define REP(i,n) for(int i=0;i<(n);i++)
#define eb emplace_back
#define pb push_back
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(),a.end()
const int INF = 0x3f3f3f3f;
int n,k;
bool adj[maxn][maxn];

set<int> zero;
set<int> st;

vector<int> a;
vector<int> b;

int seg[maxn*4]; // store the minimum
int tg[maxn*4];

void push(int i){
	seg[i*2]+=tg[i];
	tg[i*2]+=tg[i];
	seg[i*2+1]+=tg[i];
	tg[i*2+1]+=tg[i];
	tg[i]=0;
}

void mdf(int i,int l,int r,int ql,int qr, int delta){
	if(l>=qr||ql>=r) return;
	if(ql<=l&&r<=qr){
		seg[i]+=delta;
		tg[i]+=delta;
		return;
	}
	int mid=(l+r)/2;
	push(i);
	mdf(i*2,l,mid,ql,qr,delta);
	mdf(i*2+1,mid,r,ql,qr,delta);
	seg[i] = min(seg[i*2],seg[i*2+1]);
}

void reset(int i,int l,int r){
	seg[i]=tg[i]=0;
	if(l!=r-1){
		int mid=(l+r)/2;
		reset(i*2,l,mid);
		reset(i*2+1,mid,r);
	}
}

int get_idx(int i,int l,int r){
	if(l==r-1) return l;
	int mid=(l+r)/2;
	push(i);
	if(seg[i*2]==seg[i]) return get_idx(i*2,l,mid);
	else return get_idx(i*2+1,mid,r);
}

void add(int i){ // adding i to zero while maintaining st
	if(zero.count(i))return;
	// cout<<"adding: "<<i<<endl;

	auto it = zero.lower_bound(i);

	if(SZ(zero)==0){
		zero.insert(i);
	}
	else if(it==zero.end()){
		int pre = *prev(zero.end());
		if(i-pre>=k) st.insert(i);
	}
	else if(it==zero.begin()){
		if((*it) - i >=k){
			st.insert((*zero.begin()));
		}
	}
	else{
		int pre = *prev(it);
		int nxt = *it;

		if(nxt-pre>=k){
			st.erase(nxt);
		}

		if(i-pre>=k) st.insert(i);
		if(nxt - i >=k){
			st.insert(nxt);
		}
	}
	zero.insert(i);
}

void rm(int i){ // removing i to zero while maintaining st
	if(!zero.count(i)) return;
	// cout<<"removing: "<<i<<endl;
	zero.erase(i);
	auto it = zero.lower_bound(i);

	if(it==zero.end()){
		st.erase(i);
	}
	else if(it==zero.begin()){
		st.erase(*it);
	}
	else{
		int pre = *prev(it);
		int nxt = *it;

		if(i-pre>=k) st.erase(i);
		if(nxt - i >=k){
			st.erase(nxt);
		}

		if(nxt-pre>=k){
			st.insert(nxt);
		}

	}

}

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

	{
		zero.clear();
		st.clear();
		vector<int> r = _r;
		REP(j,n){
			if(r[j]==0) zero.insert(j),zero.insert(j+n);
		}
		{
			int pre = -1;
			for(int i:zero){
				if(pre!=-1&&i-pre>=k){
					st.insert(i);
				}
				pre = i;
			}
		}

		REP(i,n){
			mdf(1,0,n,i,i+1,(r[i])?r[i]:INF);
		}

		REP(i,n){
			int tmp = *st.begin();
			tmp%=n;
			// cout<<"found: "<<tmp<<endl;
			a.pb(tmp);
			st.erase(tmp);
			st.erase(tmp+n);
			rm(tmp);
			rm(tmp+n);

			int l = (tmp-(k-1)+n)%n, r = tmp;
			if(l<r){
				mdf(1,0,n,l,r,-1);
			}
			else{
				mdf(1,0,n,l,n,-1);
				mdf(1,0,n,0,r,-1);
			}

			while(seg[1] == 0){
				int cur = get_idx(1,0,n);
				// cout<<"new: "<<cur<<endl;
				add(cur);
				add(cur+n);
				mdf(1,0,n,cur,cur+1,INF);
			}
			// cout<<"zero: ";
			// for(int j:zero) cout<<j<<' ';
			// cout<<'\n';
			// cout<<"st: ";
			// for(int j:st) cout<<j<<' ';
			// cout<<'\n';
		}

		// REP(i,n) cout<<a[i]<<" \n"[i==n-1];
		// cout<<endl;
	}

	{
		reset(1,0,n);
		zero.clear();
		st.clear();
		vector<int> r = _r;
		REP(i,n) r[i] = (k-1-r[i]);
		// REP(i,n) cout<<r[i]<<" \n"[i==n-1];
		REP(j,n){
			if(r[j]==0) zero.insert(j),zero.insert(j+n);
		}
		{
			int pre = -1;
			for(int i:zero){
				if(pre!=-1&&i-pre>=k){
					st.insert(i);
				}
				pre = i;
			}
		}

		REP(i,n){
			mdf(1,0,n,i,i+1,(r[i])?r[i]:INF);
		}

		REP(i,n){
			int tmp = *st.begin();
			tmp%=n;
			// cout<<"found: "<<tmp<<endl;
			b.pb(tmp);
			st.erase(tmp);
			st.erase(tmp+n);
			rm(tmp);
			rm(tmp+n);

			int l = (tmp-(k-1)+n)%n, r = tmp;
			if(l<r){
				mdf(1,0,n,l,r,-1);
			}
			else{
				mdf(1,0,n,l,n,-1);
				mdf(1,0,n,0,r,-1);
			}

			while(seg[1] == 0){
				int cur = get_idx(1,0,n);
				// cout<<"new: "<<cur<<endl;
				add(cur);
				add(cur+n);
				mdf(1,0,n,cur,cur+1,INF);
			}
			// cout<<"zero: ";
			// for(int j:zero) cout<<j<<' ';
			// cout<<'\n';
			// cout<<"st: ";
			// for(int j:st) cout<<j<<' ';
			// cout<<'\n';
		}

		// REP(i,n) cout<<b[i]<<" \n"[i==n-1];
	}

	{
		bool vis[maxn]={0};
		for(int i:a){
			for(int j=i+1;j<i+k;j++){
				// cout<<i<<' '<<j<<endl;
				int t = j%n;
				if(!vis[t]){
					adj[i][t]=1;
				}
			}
			vis[i]=1;
		}
	}
	{
		bool vis[maxn]={0};
		for(int i:b){
			for(int j=i+1;j<i+k;j++){
				int t = j%n;
				if(!vis[t]){
					adj[t][i]=1;
				}
			}
			vis[i]=1;
		}
	}

	// REP(i,n) REP(j,n) cout<<adj[i][j]<<" \n"[j==n-1];

	REP(j,n) REP(i,n) REP(k,n){
		if(adj[i][j]&&adj[j][k]) adj[i][k] = 1;
	}

	return;
}


int compare_plants(int x, int y) {
	if(adj[x][y]) return 1;
	else if(adj[y][x]) return -1;
	else return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Runtime error 65 ms 7416 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 52 ms 5428 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 44 ms 1024 KB Output is correct
8 Correct 59 ms 1020 KB Output is correct
9 Correct 49 ms 1016 KB Output is correct
10 Correct 63 ms 1016 KB Output is correct
11 Correct 49 ms 1016 KB Output is correct
12 Correct 48 ms 1016 KB Output is correct
13 Correct 59 ms 1016 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Runtime error 65 ms 7416 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -