oj.uz

Submission #582642

# Submission time Handle Problem Language Result Execution time Memory
582642 2022-06-24T07:54:04 Z almothana05 Comparing Plants (IOI20_plants) C++14
0 / 100
 1 ms 312 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int seg[900000] , lazy[900000] , num[200000];
void mach(int id , int l , int r){
	seg[id] += lazy[id];
	if(l != r){
		lazy[id * 2] += lazy[id];
		lazy[id * 2 + 1] += lazy[id];
	}
	lazy[id] = 0;
}
int sucher(int id , int l , int r , int gewl , int gewr){
	mach(id , l , r);
	// cout << l << ' ' << r << "\n" << seg[id] << "\n";
	int m = (l + r)/2;
	if(l > gewr || gewl > r){
		return mod;
	}
	if(gewl <= l && r <= gewr){
		if(seg[id] == 0){
			if(l == r){
				return l - 1;
			}

				mach(id * 2 , l , m);
			if(seg[id * 2] == 0){
				return sucher(id * 2 , l , m , gewl , gewr);
			}
			else{
				return sucher(id * 2 + 1 , m + 1 , r , gewl , gewr);
			}
		}
		else{
			return mod;
		}
	}
	return min(sucher(id * 2 , l , m , gewl , gewr) , sucher(id * 2 + 1 , m + 1 , r , gewl , gewr));
}

void up(int id , int l , int r , int gewl , int gewr){
	// cout <<id << ' ' << l << ' ' << r << "\n";
	mach(id , l , r);
	int m = (l + r)/2;
	if(l > gewr || gewl > r){
		return;
	}
	if(gewl <= l && r <= gewr){
		seg[id]--;
		// cout << seg[id] << "\n";
		if(l != r){
			lazy[id * 2]--;
			lazy[id * 2 + 1]--; 
		}
		return;
	}
	// cout << "hop\n";
	up(id * 2 , l , m , gewl , gewr);
	up(id * 2 + 1 , m + 1 , r , gewl , gewr);
	seg[id] = min(seg[id * 2] , seg[id * 2 + 1]);
	// cout << seg[id] << "\n";
}



void init(int k, std::vector<int> r) {
	int len , cmp , menge = r.size() , erg;
	for(len  =1 ; len < r.size() ; len *= 2);

	for(int i = 0 ; i < r.size() ; i++){
		seg[i + len] = r[i];
	}
	for(int i = r.size() ; i < len ; i++){
		seg[i + len] = mod;
	}
	for(int i = len - 1; i > 0 ; i--){
		seg[i] = min(seg[i * 2] , seg[i * 2 + 1]);
	}
	for(int u = 0 ; u < r.size() ; u++){
	// cout << "ja\n";
		int pl = sucher(1 , 1 , len , 1 , len) ;
		cmp = (pl + k) % menge;
		if(cmp < pl){
			erg = sucher(1 , 1 , len , cmp + 1 , pl + 1 );
		}
		else{
			erg = sucher(1 , 1 , len , cmp + 1 , len);
			if(erg == mod){
				erg = sucher(1 , 1 , len , 1 , pl + 1);
			}
		}
			// cout << pl << "\n";
		if(erg != mod){
			pl = erg;
		}
		// cout << pl << "\n\n\n";
		num[pl] = u + 1;
		seg[pl + len] = mod;
		for(int i = (pl + len) / 2 ; i > 0 ; i /= 2){
			seg[i] = min(seg[i * 2] , seg[i * 2 + 1] );
		}
		cmp = pl - k + 1;
		cmp += menge;
		cmp %= menge;
		if(cmp < pl){
			 up(1 , 1 , len , cmp + 1 , pl + 1 );
		}
		else{
			// cout << cmp + 1 << "\n";
			up(1 , 1 , len , cmp + 1 , len);
			// cout << "\n\n";
			// cout << pl + 1 << "\n";
			up(1 , 1 , len , 1 , pl + 1);
		}

	}
}

int compare_plants(int x, int y) {
	if(num[x- 1] < num[y - 1]){
		return 1;
	}
	return -1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(len  =1 ; len < r.size() ; len *= 2);
      |                ~~~~^~~~~~~~~~
plants.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0 ; i < r.size() ; i++){
      |                  ~~^~~~~~~~~~
plants.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int u = 0 ; u < r.size() ; u++){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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