oj.uz

Submission #307999

# Submission time Handle Problem Language Result Execution time Memory
307999 2020-09-29T17:48:48 Z AKaan37 Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 21100 KB 
#include "plants.h"
//Bismillahirrahmanirrahim

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=0;i<n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 2000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;

int m,b[li],a[li],flag,t,siz[li],say,vis[li],dep[li],kk,lazy[li*4],nn;
int cev;
PII tree[li*4];
string s;
vector<int> v[li],vv;

inline void build(int node,int start,int end){
	if(start==end){
		tree[node]={vv[start],start};
		return ;
	}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	tree[node]=min(tree[node*2],tree[node*2+1]);
}

inline void push(int node,int start,int end){
	if(lazy[node]==0)return;
	tree[node].fi+=lazy[node];
	if(start!=end){
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	lazy[node]=0;
}

inline void update(int node,int start,int end,int l,int r){
	push(node,start,end);
	if(start>end || start>r || end<l || l>r || r>nn || l<1 || l>nn)return;
	if(start>=l && end<=r){
		lazy[node]--;
		push(node,start,end);
		return;
	}
	update(node*2,start,mid,l,r),update(node*2+1,mid+1,end,l,r);
	tree[node]=min(tree[node*2],tree[node*2+1]);
}

inline void update2(int node,int start,int end,int l,int r){
	push(node,start,end);
	if(start>end || start>r || end<l || l>r || r>nn || l<1 || l>nn)return;
	if(start>=l && end<=r){
		tree[node].fi=inf;
		return;
	}
	update2(node*2,start,mid,l,r),update2(node*2+1,mid+1,end,l,r);
	tree[node]=min(tree[node*2],tree[node*2+1]);
}

inline PII query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l || l>r || r>nn || l<1 || l>nn)return {inf,inf};
	push(node,start,end);
	if(start>=l && end<=r)return tree[node];
	//~ cout<<node<<" : e; "<<l<<" : ; "<<r<<endl;
	return min(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}

inline void dfs(int node,int der){
	if(vis[node])return;
	vis[node]=say;
	dep[node]=der;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		dfs(go,der+1);
	}
}

void init(int k, std::vector<int> r) {
	for(int i=0;i<(int)r.size();i++){
		if(r[i]==1){
			v[(i+1)%(int)r.size()].pb(i);
			siz[i]++;
		}
	}
	//~ queue<int>
	//~ int n=(int)r.size();
	//~ FOR{
		//~ if(siz[i]==0){
			//~ say++;
			//~ dfs(i,0);
		//~ }
	//~ }
	vv.pb(0);
	for(int i=0;i<(int)r.size();i++)vv.pb(r[i]);
	//~ vv=r;
	say=0;
	kk=k;
	int n=(int)vv.size()-1;
	build(1,1,n);
	nn=n;
	for(int i=1;i<(int)vv.size();i++){
		int ind=-1;
		ind=query(1,1,n,1,n).se;
		while(1){
			flag=0;
			//~ cout<<ind<<endl;
			if(query(1,1,n,max(1,min(ind-1,ind-k+1)),ind-1).fi==0){ind=query(1,1,n,max(1,min(ind-1,ind-k+1)),ind-1).se;flag=1;}
			//~ cout<<max(ind+1,ind-k+1+n-1)<<endl;
			if(query(1,1,n,max(ind+1,ind-k+1+n),n).fi==0){ind=query(1,1,n,max(ind+1,ind-k+n+1),n).se;flag=1;}
			//~ cout<<ind<<endl;
			
			if(!flag)break;
		}
		//~ cout<<ind<<"**"<<endl;
			update(1,1,n,max(1,min(ind-1,ind-k+1)),ind-1);
			update(1,1,n,max(ind+1,ind-k+n+1),n);
			update2(1,1,n,ind,ind);
			vis[ind]=++say;
			continue;
		
	}
}

int compare_plants(int x, int y) {
	x++;
	y++;
	if(vis[x]<vis[y])return 1;
	if(vis[x]>vis[y])return -1;
	if(vis[x]==vis[y]){
		//~ cout<<x<<" : : "<<y<<" : ;"<<vis[x]<<" : : "<<vis[y]<<endl;
		return 0;
	}
	if(vis[x]!=vis[y])return 0;
	if(dep[x]>dep[y])return -1;
	return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Incorrect 3 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 83 ms 8352 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 83 ms 8312 KB Output is correct
11 Correct 79 ms 8312 KB Output is correct
12 Correct 79 ms 8440 KB Output is correct
13 Correct 83 ms 8312 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 83 ms 8352 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 83 ms 8312 KB Output is correct
11 Correct 79 ms 8312 KB Output is correct
12 Correct 79 ms 8440 KB Output is correct
13 Correct 83 ms 8312 KB Output is correct
14 Correct 119 ms 9548 KB Output is correct
15 Correct 640 ms 21100 KB Output is correct
16 Correct 119 ms 9644 KB Output is correct
17 Correct 641 ms 21100 KB Output is correct
18 Correct 370 ms 21012 KB Output is correct
19 Correct 377 ms 20972 KB Output is correct
20 Correct 547 ms 21100 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 112 ms 7948 KB Output is correct
4 Execution timed out 4061 ms 18304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 3 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Incorrect 3 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Incorrect 3 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -