oj.uz

Submission #1053979

# Submission time Handle Problem Language Result Execution time Memory
1053979 2024-08-12T01:37:46 Z pcc Comparing Plants (IOI20_plants) C++17
44 / 100
 632 ms 57956 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 4e5+10;

int arr[mxn];
int N;
int K;
int perm[mxn];
int dp[mxn];
set<int> st;
set<pii> rng;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	pii seg[mxn*4];
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].fs = min(seg[ls].fs+seg[ls].sc,seg[rs].fs+seg[rs].sc);
		return;
	}
	int get_mn(int now,int l,int r){
		if(l == r){
			return l;
		}
		if(seg[ls].fs+seg[ls].sc<seg[rs].fs+seg[rs].sc)return get_mn(ls,l,mid);
		else return get_mn(rs,mid+1,r);
	}
#undef ls
#undef rs
#undef mid
}seg;


void add(int p){
	int nxt = *st.upper_bound(p);
	int pre = *(--st.upper_bound(p));
	rng.erase(pii(nxt-pre,nxt));
	rng.insert(pii(nxt-p,nxt));
	rng.insert(pii(p-pre,p));
	st.insert(p);
	return;
}

void del(int p){
	auto it = st.find(p);
	int pre = *prev(it),nxt = *next(it);
	rng.erase(pii(p-pre,p));
	rng.erase(pii(nxt-p,nxt));
	rng.insert(pii(nxt-pre,nxt));
	st.erase(p);
	return;
}

void calc(int id){
	auto it = rng.rbegin();
	if(it->sc >= N*2)it++;
	auto pos = it->sc;
	pos %= N;
	//cerr<<id<<":"<<pos<<','<<it->fs<<endl;
	assert(it->fs>=K);
	del(pos);
	del(pos+N);
	perm[pos] = id;
	seg.modify(0,0,N*2-1,pos+N-K+1,pos+N,-1);
	seg.modify(0,0,N*2-1,max(pos-K+1,0),pos,-1);
	if(pos-K+1<0)seg.modify(0,0,N*2-1,N*2-1+(pos-K+1)+1,N*2-1,-1);
	while(seg.seg[0].fs+seg.seg[0].sc == 0){
		int p = seg.get_mn(0,0,N*2-1);
		p %= N;
		add(p);
		seg.modify(0,0,N*2-1,p,p,mxn*4);
		add(p+N);
		seg.modify(0,0,N*2-1,p+N,p+N,mxn*4);
	}
	return;
}

void init(int k, std::vector<int> r) {
	K = k;
	N = r.size();
	for(int i = 0;i<N;i++)arr[i] = arr[i+N] = r[i];
	int pre = -1;
	st.insert(-1);
	st.insert(N*2);
	rng.insert(pii(N*2+1,N*2));
	for(int i = 0;i<N*2;i++){
		if(!arr[i]){
			add(i);
		}
		if(arr[i])seg.modify(0,0,N*2-1,i,i,arr[i]);
		else seg.modify(0,0,N*2-1,i,i,mxn*4);
	}
	//cerr<<"INIT!: "<<rng.rbegin()->fs<<endl;
	//for(auto &i:rng)cerr<<i.fs<<','<<i.sc<<endl;
	for(int i = N-1;i>=0;i--)calc(i);
	//for(int i = 0;i<N;i++)cerr<<perm[i]<<',';cerr<<endl;
}

int compare_plants(int x, int y) {
	return perm[x]>perm[y]?1:-1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:95:6: warning: unused variable 'pre' [-Wunused-variable]
   95 |  int pre = -1;
      |      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4440 KB Output is correct
3 Correct 1 ms 4540 KB Output is correct
4 Incorrect 1 ms 4444 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 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4648 KB Output is correct
7 Correct 32 ms 9460 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 34 ms 9540 KB Output is correct
11 Correct 38 ms 9816 KB Output is correct
12 Correct 30 ms 9468 KB Output is correct
13 Correct 35 ms 9556 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4648 KB Output is correct
7 Correct 32 ms 9460 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 34 ms 9540 KB Output is correct
11 Correct 38 ms 9816 KB Output is correct
12 Correct 30 ms 9468 KB Output is correct
13 Correct 35 ms 9556 KB Output is correct
14 Correct 55 ms 10576 KB Output is correct
15 Correct 330 ms 20820 KB Output is correct
16 Correct 53 ms 10576 KB Output is correct
17 Correct 309 ms 20820 KB Output is correct
18 Correct 632 ms 39272 KB Output is correct
19 Correct 207 ms 20984 KB Output is correct
20 Correct 278 ms 21076 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4544 KB Output is correct
3 Correct 29 ms 9204 KB Output is correct
4 Correct 351 ms 32744 KB Output is correct
5 Correct 339 ms 22992 KB Output is correct
6 Correct 366 ms 20764 KB Output is correct
7 Correct 360 ms 20824 KB Output is correct
8 Correct 330 ms 20820 KB Output is correct
9 Correct 395 ms 29780 KB Output is correct
10 Correct 348 ms 23380 KB Output is correct
11 Correct 545 ms 57956 KB Output is correct
12 Correct 186 ms 20304 KB Output is correct
13 Correct 580 ms 46676 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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