제출 #588319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588319		almothana05	식물 비교 (IOI20_plants)	C++14	0 / 100	1 ms	468 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int seg[900000] , lazy[900000] , num[500000];
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++){
		erg = mod;
	// cout << "ja\n";
		int pl = sucher(1 , 1 , len , 1 , len) ;
		// cout << pl << "\n";
		assert(pl != mod);
		cmp = (pl + k) % menge;
		// cout << cmp << "\n";
		if(cmp <= pl){
			erg = sucher(1 , 1 , len , cmp + 1 , pl );
			// cout << erg << "\n";
		}
		else{
			erg = sucher(1 , 1 , len , cmp + 1 , len);
			if(erg > menge){
				erg = sucher(1 , 1 , len , 1 , pl);
			}
		}
			// cout << pl << "\n";
		if(erg < menge){
			pl = erg;
		}
		// cout << pl << "\n\n\n";
		num[pl] = u + 1;
		// cout << pl << ' ';
		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 );
		}
		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);
		}
 
	}
	// cout << "\n";
}
 
int compare_plants(int x, int y) {
	if(num[x] < num[y]){
		return 1;
	}
	return -1;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25