Submission #1172516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172516		hyakup	식물 비교 (IOI20_plants)	C++20	27 / 100	247 ms	17672 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
vector<int> h;

const int inf = 1e9;

class segment_tree{
public:

	int id_max(){ return seg[1].maxi.second; }
	void update( int l, int r, int val ){ update( 1, 0, n - 1, l, r, val ); }
	segment_tree( vector<int>& v, int k ): n(v.size()), k(k) { seg.resize(4*v.size()); build( 1, 0, n - 1, v );  }
private:
  int n, k;
	struct Node{
		pii maxi;
		int lazy = 0, aux = 0;
		Node( pii maxi = pii(0, 0), int k = 0 ) : maxi(maxi), aux(k) {}
		Node operator + ( Node n ) const {
			if( maxi.first > n.maxi.first ) return *this;
			if( maxi.first < n.maxi.first ) return n;
			if( maxi.second + aux - 1 >= n.maxi.second ) return *this;
			return n;
		}
	};
	vector<Node> seg;
	void build( int pos, int ini, int fim, vector<int>& v ){
		if( ini == fim ){ seg[pos] = Node( pii( v[ini], ini ), k ); return; }
		int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
		build( l, ini, mid, v ); build( r, mid + 1, fim, v );
		seg[pos] = seg[l] + seg[r];
	}

	void refresh( int pos, int ini, int fim ){
		if( seg[pos].lazy == 0 ) return;
		int x = seg[pos].lazy; seg[pos].lazy = 0;
		seg[pos].maxi.first += x;
		if( ini == fim ) return;
		seg[2*pos].lazy += x;
		seg[2*pos + 1].lazy += x;
	}

	void update( int pos, int ini, int fim, int ki, int kf, int val ){
		refresh( pos, ini, fim );
		if( ki > fim || ini > kf ) return;
		if( ki <= ini && fim <= kf ){
			seg[pos].lazy += val; refresh( pos, ini, fim );
			return;
		}
		int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
		update( l, ini, mid, ki, kf, val ); update( r, mid + 1,fim, ki, kf, val );
		seg[pos] = seg[l] + seg[r];
	}
};

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

	h.resize(n);

	for( int i = 0; i < n; i++ ){
		int id = seg.id_max();

		seg.update( id, id, -inf );
		seg.update( id - k + 1, id - 1, 1 );
		if( id - k + 1 < 0 ) seg.update( n + id - k + 1, n - 1, 1 );
		h[id] = i;
	}
	return;
}

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

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