Submission #300905

#	Time	Username	Problem	Language	Result	Execution time	Memory
300905		aljasdlas	Comparing Plants (IOI20_plants)	C++14	0 / 100	77 ms	3320 KiB

plants

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

vector<int> b;
int N;
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;
  	return l.first <= r.first ? l : r;                 // Min
  }
  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) {
	b = r;
	int n = b.size();
	N = 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;
}

int compare_plants(int x, int y) {
	return a[x] > a[y] ? 1 : -1;
	// return 0;
}

• 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