oj.uz

Submission #751768

# Submission time Handle Problem Language Result Execution time Memory
751768 2023-06-01T12:16:12 Z tolbi Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 17004 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#ifdef tolbi
#else
#include "plants.h"
#endif
vector<int> arr;
set<int> zer;
struct SegTree{
	vector<int> segtree;
	vector<int> lazy;
	int _n;
	SegTree(int n):_n(n){
		segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
		lazy.resize(segtree.size(),0ll);
	}
	void dallan(int node){
		segtree[node]+=lazy[node];
		if (node*2+1<segtree.size()){
			lazy[node*2+1]+=lazy[node];
			lazy[node*2+2]+=lazy[node];
		}
		lazy[node]=0ll;
	}
	void update(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr) {
			lazy[node]+=val;
			dallan(node);
			return;
		}
		if (l>tarr || r<tarl) return;
		int mid = l+(r-l)/2;
		update(tarl, tarr, val, l, mid, node*2+1);
		update(tarl, tarr, val, mid+1, r, node*2+2);
		segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
	}
	int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return INF;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return min(lnode, rnode);
	}
	int proc(int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (segtree[node]>0) return -1;
		if (l==r){
			int ind = node-segtree.size()/2;
			if (ind<_n) zer.insert(ind);
			segtree[node]=_n+23;//////////////////////////////////////////////////////////////////birakma bunu burda
			return ind;
		}
		int mid = l+(r-l)/2;
		int lnode = proc(l, mid, node*2+1);
		int rnode = proc(mid+1, r, node*2+2);
		if (lnode==-1) return rnode;
		return lnode;
	}
	void debug(){
		for (int i = 0; i < _n; i++){
			cout<<query(i, i)<<" ";
		}
		cout<<endl;
		coutarr(segtree);
	}
};
void init(int32_t k, vector<int32_t> r) {
	int n = r.size();
	auto check = [&](int x)->bool{
		if (x==-1) return false;
		auto it = zer.find(x);
		if (it==zer.end()) return false;
		if (zer.size()==1) return true;
		auto it2 = it;
		if (it==zer.begin()) it2=zer.end();
		it2--;
		int el1 = *it;
		int el2 = *it2;
		if (el1>=el2){
			if (el1-el2<=k-1){
				return false;
			}
		}
		else {
			if (el1+(n-el2)<=k-1){
				return false;
			}
		}
		return true;
	};
	arr.resize(n);
	SegTree segtree(n);
	for (int i = 0; i < n; ++i)
	{
		segtree.update(i,i,r[i]);
	}
	segtree.proc();
	int node = -1;
	auto it = zer.begin();
	while (it!=zer.end()) {
		if (check(*it)) node=*it;
		it++;
	}
	int i = 0;
	while (i<n){
		arr[node]=i++;
		zer.erase(node);
		int pot1 = -1;
		if (zer.size()){
			if (zer.lower_bound(node)==zer.end()){
				pot1 = *zer.begin();
			}
			else pot1 = *zer.lower_bound(node);
		}
		int pot2 = -1;
		if (node>=k-1){
			segtree.update(node-k+1,node-1,-1);
			pot2=segtree.proc();
		}
		else {
			segtree.update(0,node-1,-1);
			pot2=segtree.proc();
			segtree.update(n+node-k+1,n-1,-1);
			int lel = segtree.proc();
			if (lel!=-1) pot2=lel;
		}
		if (pot1==-1 && pot2==-1){
			node=-1;
			continue;
		}
		if (check(pot1)) node=pot1;
		else node=pot2;
	}
}
int32_t compare_plants(int32_t x, int32_t y) {
	if (arr[x]<arr[y]) return 1;
	return -1;
}



#ifdef tolbi
static int32_t _n, k, q;
static vector<int32_t> r;
static  vector<int32_t> x;
static  vector<int32_t> y;
static  vector<int32_t> answer;
int32_t main() {
	assert(scanf("%d%d%d", &_n, &k, &q) == 3);
	r.resize(_n);
	answer.resize(q);
	for (int32_t i = 0; i < _n; i++) {
		int32_t value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int32_t i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int32_t i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int32_t i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}
#endif

Compilation message

plants.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
plants.cpp: In member function 'void SegTree::dallan(long long int)':
plants.cpp:52:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if (node*2+1<segtree.size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 20 ms 440 KB Output is correct
7 Correct 636 ms 5192 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 19 ms 440 KB Output is correct
10 Correct 629 ms 5164 KB Output is correct
11 Correct 481 ms 5236 KB Output is correct
12 Correct 471 ms 5320 KB Output is correct
13 Correct 385 ms 5128 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 20 ms 440 KB Output is correct
7 Correct 636 ms 5192 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 19 ms 440 KB Output is correct
10 Correct 629 ms 5164 KB Output is correct
11 Correct 481 ms 5236 KB Output is correct
12 Correct 471 ms 5320 KB Output is correct
13 Correct 385 ms 5128 KB Output is correct
14 Execution timed out 4074 ms 6092 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 101 ms 3152 KB Output is correct
4 Execution timed out 4090 ms 17004 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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