oj.uz

Submission #301386

# Submission time Handle Problem Language Result Execution time Memory
301386 2020-09-17T21:45:50 Z aljasdlas Comparing Plants (IOI20_plants) C++14
27 / 100
 554 ms 16120 KB 
#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();
	
	// int m = 5;
	// k = 2;
	// int offset = 0;

	// vector<int> actual(m);

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

	// r.assign(m, 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;

	k=k_;r=r_;n=r.size();
	b = r;
	int n = b.size();
	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(auto x: a)
	// 	cerr << x << " ";
	// cerr << 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]-sum[x] == 0) 
			isX = 1;
		if(sum[y]-sum[x] == 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;
		if(isX) ans += X;
		if(isY) ans -= X;
		return ans;
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 80 ms 3356 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 77 ms 3416 KB Output is correct
11 Correct 74 ms 3288 KB Output is correct
12 Correct 75 ms 3416 KB Output is correct
13 Correct 79 ms 3316 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 80 ms 3356 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 77 ms 3416 KB Output is correct
11 Correct 74 ms 3288 KB Output is correct
12 Correct 75 ms 3416 KB Output is correct
13 Correct 79 ms 3316 KB Output is correct
14 Correct 110 ms 3960 KB Output is correct
15 Correct 554 ms 16116 KB Output is correct
16 Correct 113 ms 3960 KB Output is correct
17 Correct 554 ms 16120 KB Output is correct
18 Correct 377 ms 16120 KB Output is correct
19 Correct 379 ms 15992 KB Output is correct
20 Correct 502 ms 16120 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -