oj.uz

Submission #300973

# Submission time Handle Problem Language Result Execution time Memory
300973 2020-09-17T15:34:32 Z aljasdlas Comparing Plants (IOI20_plants) C++14
27 / 100
 619 ms 15384 KB 
#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.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 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 79 ms 3360 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 78 ms 3288 KB Output is correct
11 Correct 77 ms 3360 KB Output is correct
12 Correct 75 ms 3484 KB Output is correct
13 Correct 74 ms 3364 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 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 79 ms 3360 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 78 ms 3288 KB Output is correct
11 Correct 77 ms 3360 KB Output is correct
12 Correct 75 ms 3484 KB Output is correct
13 Correct 74 ms 3364 KB Output is correct
14 Correct 118 ms 3960 KB Output is correct
15 Correct 619 ms 15268 KB Output is correct
16 Correct 108 ms 3960 KB Output is correct
17 Correct 553 ms 15352 KB Output is correct
18 Correct 376 ms 15376 KB Output is correct
19 Correct 379 ms 15224 KB Output is correct
20 Correct 512 ms 15384 KB Output is correct

Subtask #4
0 / 17.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 71 ms 3320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 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 1 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -