제출 #301398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301398		aljasdlas	식물 비교 (IOI20_plants)	C++14	32 / 100	965 ms	16056 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> b, r;
int N, n;
int K, k;
struct SegmentTreeLazy {
  vector<int> lazy;
  vector<pair<int,int>> st;
  SegmentTreeLazy(int _N) {
    st.resize(4*_N);
    lazy.assign(4*_N, 0);                      // Add to All
    build();
  }
  inline pair<int,int> op(pair<int,int> l, pair<int,int> r) {
	if(l.second == -1) return r;
	if(r.second == -1) return l;
	if(l.first < r.first) return l;
	if(r.first < l.first) return r;
	
	if(l.second > r.second) swap(l, r);
	if(l.second + K-1 >= r.second) return l;
	return r;
  }
  void build(int id=1,int l=0,int r=N) {
    if(l+1 == r) {
      st[id] = make_pair(b[l], l);
      return;
    }
    int mid = (l+r)/2;
    build(id*2  , l, mid);
    build(id*2+1, mid, r);
    st[id] = op(st[id*2], st[id*2+1]);
  }
  void upd(int id, int l, int r, int val) {
    lazy[id] += val;                           // Add To All
    if(l+1 == r) // Update value of b[l]
      b[l] += val;                             // Add to All
    st[id].first += val;                         // Add to Min/Max
  }
  void shift(int id, int l, int r) {
    int mid = (l+r)/2;
    upd(id*2  , l, mid, lazy[id]);
    upd(id*2+1, mid, r, lazy[id]);
    lazy[id] = 0;                              // Add To All
  }
  void modify(int x,int y,int val,int id=1,int l=0,int r=N){
    if(x >= r || y <= l) return;
    if(x <= l && y >= r) {
      upd(id, l, r, val);
      return;
    }
    shift(id, l, r);
    int mid = (l+r)/2;
    modify(x, y, val, id*2  , l, mid);
    modify(x, y, val, id*2+1, mid, r);
    st[id] = op(st[id*2], st[id*2+1]);
  }
  pair<int,int> query(int x, int y, int id=1,int l=0,int r=N) {
    if(x >= r || y <= l) return {-1,-1};               // Min/Max
    if(x <= l && y >= r) return st[id];
    shift(id, l, r);
    int mid = (r+l)/2;
    return op(query(x, y, id*2  , l, mid),
              query(x, y, id*2+1, mid, r));
  }
};

vector<int> a;

vector<int> sum;

void init(int k_, vector<int> r_) {
	k=k_;r=r_;n=r.size();
	
	// n = 5;
	// k = 2;
	// int offset = 0;

	// vector<int> actual(n);

	// for(int i = 0; i < n; i++)
	// 	actual[((i)+offset+n)%n] = i;
	// // srand(0);
	// // random_shuffle(actual.begin(), actual.end());
	// // actual = {2,0,3,1};

	// r.assign(n, 0);
	// for(int i = 0; i < n; i++)
	// 	for(int j = 1; j < k; j++)
	// 		if(actual[i] < actual[(i+j)%n])
	// 			r[i]++;

	// for(auto x: actual)
	// 	cerr << x << " ";
	// cerr << endl;
	// for(auto x: r)
	// 	cerr << x << " ";
	// cerr << endl;
	// cerr << endl;

	b = r;
	N = n;
	K = k;

	if(k*2 > n) {
		SegmentTreeLazy ST(n);
		ST.build();
		a.resize(n);
		for(int i = n-1; i >= 0; i--) {

			int pos = ST.query(0, n).second;
			if(pos >= k-1) {
				ST.modify(pos-(k-1), pos, -1);
			} else {
				ST.modify(0, pos, -1);
				int y = (k-1)-pos;
				ST.modify(n-y, n, -1);
			}
			a[pos] = i;
			ST.modify(pos, pos+1, 10000000);
		}
		return;
	}


	if(k == 2) {
		sum.resize(n+1);
		sum[0] = b[0];
		for(int i = 1; i < n; i++)
			sum[i] = sum[i-1] + b[i];

		for(int i = 0; i < n; i++)
			cerr << sum[i] << " ";
		cerr << endl;
	}

	// for(auto x: a)
	// 	cerr << x << " ";
	// cerr << endl;

	// for(int i = 0; i < n; i++)
	// 	for(int j = 0; j < n; j++) {
	// 		int x = compare_plants(i, j);
	// 		if(x == 0) continue;
	// 		if(x == 1 && actual[i] > actual[j]) continue;
	// 		if(x == -1 && actual[i] < actual[j]) continue;
	// 		// cout << i << "(" << actual[i] << ")" << " " << j << "(" << actual[j] << ")" << ": " << x << endl;
	// 	}
	return;
}

int compare_plants(int x, int y) {
	if(k*2 > n)
		return a[x] > a[y] ? 1 : -1;

	if(k == 2) {
		int X = 1;
		if(x > y) {
			swap(x,y);
			X = -1;
		}

		bool isX = 0;
		bool isY = 0;
		if(sum[y-1]-(x == 0 ? 0 : sum[x-1]) == 0) 
			isX = 1;
		if(sum[y-1]-(x == 0 ? 0 : sum[x-1]) == y-x)
			isY = 1;

		if((sum[n-1]-sum[y-1]) + (x>0 ? sum[x-1] : 0) == 0)
			isY = 1;
		if((sum[n-1]-sum[y-1]) + (x>0 ? sum[x-1] : 0) == x + (n-y))
			isX = 1;
		int ans = 0;

		// cerr << sum[x] << " " << sum[y] << endl;

		if(isX) ans += X;
		if(isY) ans -= X;
		return ans;
	}

	return 0;
}

• Subtask 1: 5 / 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