oj.uz

Submission #751777

# Submission time Handle Problem Language Result Execution time Memory
751777 2023-06-01T12:47:21 Z tolbi Comparing Plants (IOI20_plants) C++17
27 / 100
 500 ms 17116 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 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);
		segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
		if (lnode==-1) return rnode;
		return lnode;
	}
};
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(int)':
plants.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   if (node*2+1<segtree.size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~
plants.cpp: In member function 'int SegTree::query(int, int, int, int, int)':
plants.cpp:75:32: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   75 |   if (l>tarr || r<tarl) return INF;
      |                                ^~~

Subtask #1
0 / 5.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 Correct 0 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 0 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 0 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 50 ms 3220 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 51 ms 3320 KB Output is correct
11 Correct 49 ms 3232 KB Output is correct
12 Correct 49 ms 3320 KB Output is correct
13 Correct 51 ms 3280 KB Output is correct

Subtask #3
13.0 / 13.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 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 50 ms 3220 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 51 ms 3320 KB Output is correct
11 Correct 49 ms 3232 KB Output is correct
12 Correct 49 ms 3320 KB Output is correct
13 Correct 51 ms 3280 KB Output is correct
14 Correct 78 ms 3384 KB Output is correct
15 Correct 472 ms 12852 KB Output is correct
16 Correct 88 ms 5636 KB Output is correct
17 Correct 500 ms 12840 KB Output is correct
18 Correct 439 ms 17116 KB Output is correct
19 Correct 398 ms 13156 KB Output is correct
20 Correct 463 ms 12860 KB Output is correct

Subtask #4
0 / 17.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 48 ms 3160 KB Output is correct
4 Incorrect 336 ms 12244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 #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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -