Submission #300973

#	Time	Username	Problem	Language	Result	Execution time	Memory
300973		aljasdlas	Comparing Plants (IOI20_plants)	C++14	27 / 100	619 ms	15384 KiB

plants

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

vector<int> b;
int N;
int 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;
void init(int k, vector<int> r) {
	/*
	int m = 9;
	k = 5;
	int offset = 1;

	vector<int> actual(m);
	for(int i = 0; i < m; i++)
		actual[((m-1-i)+offset+m)%m] = i;
	r.assign(9, 0);
	for(int i = 0; i < m; i++)
		for(int j = 1; j < k; j++)
			if(actual[i] < actual[(i+j)%m])
				r[i]++;

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

*/

	b = r;
	int n = b.size();
	N = n;
	K = k;

	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);

		// for(int j = 0; j < n; j++) {
		// 	ST.query(j,j+1);
		// 	if(b[j] > 1000000) cerr << "X ";
		// 	else cerr << b[j] << " ";
		// }
		// cerr << endl;
	}

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

	return;
}

int compare_plants(int x, int y) {
	return a[x] > a[y] ? 1 : -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