oj.uz

Submission #807735

# Submission time Handle Problem Language Result Execution time Memory
807735 2023-08-05T00:05:04 Z I_Love_EliskaM_ Comparing Plants (IOI20_plants) C++17
44 / 100
 725 ms 54308 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];
int n;
int k;

struct sgt {
	vector<pi> t;
	vector<int> lazy; 
	int sz=1;
	pi merge(pi a, pi b) {
		if (a.f > b.f) return a;
		return b;
	}
	sgt(int n) {
		while (sz<n) sz<<=1;
		t.assign(2*sz,{0,n});
		forn(i,n) t[sz-1+i]={0,i};
		lazy.assign(4*sz,0);
	}
	void push(int v) {
		t[v].f+=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]=merge(t[2*v+1],t[2*v+2]);
	}
	void add(int l, int r, int x) {
		add(0,0,sz,l,r,x);
	}
	pi query(int v, int l, int r, int lx, int rx) {
		if (lazy[v]) push(v);
		if (rx<=l || r<=lx) return {-2e9,n};
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		auto lq=query(2*v+1,l,m,lx,rx);
		auto rq=query(2*v+2,m,r,lx,rx);
		t[v]=merge(t[2*v+1],t[2*v+2]);
		return merge(lq,rq);
	}
	pi 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];

struct DSU {
	vector<int> p,sz;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
	}
	int get(int u) {
		return u==p[u]?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (u==v) return;
		if (sz[u] < sz[v]) swap(u,v);
		sz[u]+=sz[v];
		p[v]=u;
	}
};
DSU dsu(n);

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

	forn(i,n) r.pb(r[i]);
	forn(i,n) r.pb(r[i]);

	sgt st(n);
	forn(i,n) st.add(i,i+1,r[i]);

	int z;
	for (int i=n; i<2*n; ++i) {
		if (r[i]==k-1) {
			z=i;
			for (int j=i; j>z-k; --j) if (r[j]==k-1) z=j;
			break;
		}
	}

	set<int> s;
	set<int> ok;
	int ri=-1;
	for (int l=z; l<z+n; ++l) {
		if (r[l]==k-1) {
			s.insert(l%n);
			s.insert(l%n+n);
			s.insert(l%n+2*n);
			if (l>=ri) {
				ok.insert(l%n);
			}
			ri=l+k;
		}
	}

	//2 0 1 1
	//1 4 2 3|1 4

	int nxt=1;
	forn(it,n) {
		auto x=*ok.begin(); ok.erase(ok.begin());
		//cout<<"? "<<x<<'\n'; cout.flush();
		
		p[x]=nxt++;

		s.erase(x);
		s.erase(x+n);
		s.erase(x+2*n);
		st.add(x,x+1,-1e9);
		int j=x;
		if (s.size()) {
			auto it1=s.lower_bound(x);
			//for(auto&x:s) cout<<">"<<x<<' '; cout<<'\n';
			//cout<<"?? "<<(*it1)<<'\n';
			j=*it1;
		}
		j%=n;

		if (x-k+1>=0) {
			st.add(x-k+1,x,1);
		} else {
			st.add(0,x,1);
			st.add(x-k+1+n,n,1);
		}
		//forn(i,n) cout<<st.query(i,i+1).f<<' '; cout<<'\n';
		vector<int> v;
		while(1) {
			pi q;
			if (x-k+1>=0) {
				q=st.query(x-k+1,x);
			} else {
				auto q1=st.query(0,x);
				auto q2=st.query(x-k+1+n,n);
				q=st.merge(q1,q2);
			}
			//cout<<"! "<<j<<"  "<<q.f<<' '<<q.s<<'\n';
			if (q.f<k-1) break;
			if (q.s > j) {
				j+=n;
			}
			if (j-q.s>=k) {
				ok.insert(j%n);
			}
			j=q.s;
			s.insert(j);
			s.insert(j+n);
			s.insert(j+2*n);
			st.add(j,j+1,-1e9);
			v.pb(j);
		}
		if (!s.size()) break;
		for(auto&x:v) st.add(x,x+1,1e9);
		auto it2 = s.find(j+n);
		--it2;
		int t = *it2;
		if (j+n-t>=k) ok.insert(j);
	}

	//forn(i,n) cout<<p[i]<<' '; cout<<'\n';

}

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

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:113:19: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |  for (int l=z; l<z+n; ++l) {
      |                  ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Incorrect 3 ms 8532 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 5 ms 8532 KB Output is correct
2 Correct 3 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 7 ms 8660 KB Output is correct
7 Correct 57 ms 11416 KB Output is correct
8 Correct 5 ms 8532 KB Output is correct
9 Correct 7 ms 8660 KB Output is correct
10 Correct 57 ms 11428 KB Output is correct
11 Correct 53 ms 11432 KB Output is correct
12 Correct 53 ms 11936 KB Output is correct
13 Correct 56 ms 11460 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 3 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 7 ms 8660 KB Output is correct
7 Correct 57 ms 11416 KB Output is correct
8 Correct 5 ms 8532 KB Output is correct
9 Correct 7 ms 8660 KB Output is correct
10 Correct 57 ms 11428 KB Output is correct
11 Correct 53 ms 11432 KB Output is correct
12 Correct 53 ms 11936 KB Output is correct
13 Correct 56 ms 11460 KB Output is correct
14 Correct 100 ms 12312 KB Output is correct
15 Correct 725 ms 22888 KB Output is correct
16 Correct 100 ms 12384 KB Output is correct
17 Correct 702 ms 23016 KB Output is correct
18 Correct 507 ms 22992 KB Output is correct
19 Correct 613 ms 37032 KB Output is correct
20 Correct 708 ms 23020 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8528 KB Output is correct
3 Correct 46 ms 11544 KB Output is correct
4 Correct 452 ms 35268 KB Output is correct
5 Correct 531 ms 28192 KB Output is correct
6 Correct 593 ms 26520 KB Output is correct
7 Correct 650 ms 26400 KB Output is correct
8 Correct 721 ms 26720 KB Output is correct
9 Correct 466 ms 26968 KB Output is correct
10 Correct 498 ms 29020 KB Output is correct
11 Correct 366 ms 25868 KB Output is correct
12 Correct 486 ms 54308 KB Output is correct
13 Correct 473 ms 26160 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8544 KB Output is correct
2 Correct 3 ms 8532 KB Output is correct
3 Incorrect 3 ms 8532 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 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Incorrect 3 ms 8532 KB Output isn't correct
5 Halted 0 ms 0 KB -