oj.uz

Submission #300965

# Submission time Handle Problem Language Result Execution time Memory
300965 2020-09-17T15:32:43 Z shayan_p Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 5496 KB 
#include<bits/stdc++.h>
#include "plants.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 310, mod = 1e9 + 7, inf = 1e9 + 10;

int pos[maxn];
int mn[4 * maxn], lz[4 * maxn];
int n;

void shift(int l, int r, int id){
    mn[id]+= lz[id];
    if(r-l > 1)
	lz[2*id]+= lz[id], lz[2*id+1]+= lz[id];
    lz[id] = 0;
}
void build(vector<int> &v, int l = 0, int r = n, int id = 1){
    lz[id] = 0;
    if(r-l == 1){
	mn[id] = v[l];
	return;
    }
    int mid = (l+r) >> 1;
    build(v, l, mid, 2*id);
    build(v, mid, r, 2*id+1);
    mn[id] = min(mn[2*id], mn[2*id+1]);
}
void sadd(int f, int s, int x, int l = 0, int r = n, int id = 1){	
    shift(l, r, id);
    if(f >= s || l >= r || s <= l || r <= f)
	return;
    if(f <= l && r <= s){
	lz[id] = x;
	shift(l, r, id);
	return;
    }
    int mid = (l+r) >> 1;
    sadd(f, s, x, l, mid, 2*id);
    sadd(f, s, x, mid, r, 2*id+1);
    mn[id] = min(mn[2*id], mn[2*id+1]);
}
int go(int l = 0, int r = n, int id = 1){
    shift(l, r, id);
    if(mn[id] > 0)
	return r;
    if(r-l == 1)
	return l;
    int mid = (l+r) >> 1;
    int ans = go(l, mid, 2*id);
    if(ans == mid)
	ans = go(mid, r, 2*id+1);
    return ans;    
}

bool can[maxn][maxn];

void again(int k, vector<int> a, int X){
    set<int> ids;
    set<pii> did;

    build(a);
    auto minim = [&](){
		     return mn[1];
		 };
    auto find = [&](){    
		     return go();
		};
    auto neg = [&](int p){
		   if(p >= k-1)
		       sadd(p-k+1, p+1, -1);
		   else
		       sadd(0, p+1, -1), sadd((p-k+1 + n) % n, n, -1);
	       };
    
    auto add = [&](int p){
		   sadd(p, p+1, inf);
		   if(ids.empty()){
		       ids.insert(p);
		       did.insert({n, p});
		       return;
		   }
		   ids.insert(p);
		   auto it = ids.find(p);
		   auto L = (it == ids.begin() ? --ids.end() : prev(it));
		   auto R = (next(it) == ids.end() ? ids.begin() : next(it));
		   int DIS = ((*R) - (*L) + n) % n;
		   if(DIS == 0)
		       DIS = n;
		   did.erase({DIS, *R});
		   did.insert({((*R) - p + n) % n, *R});
		   did.insert({(p - (*L) + n) % n, p});
	       };
    auto era = [&](int p){
		   if(sz(ids) == 1){
		       ids.clear();
		       did.clear();
		       return;
		   }
		   auto it = ids.find(p);
		   auto L = (it == ids.begin() ? --ids.end() : prev(it));
		   auto R = (next(it) == ids.end() ? ids.begin() : next(it));
		   int DIS = ((*R) - (*L) + n) % n;
		   if(DIS == 0)
		       DIS = n;
		   did.erase({((*R) - p + n) % n, *R});
		   did.erase({(p - (*L) + n) % n, p});
		   did.insert({DIS, *R});
		   ids.erase(p);
	       };
    for(int C = 0; C < n; C++){
	while(minim() == 0)
	    add(find());
	if(sz(did) == 0)
	    break;
	auto it = --did.end();
	int p = it->S;
	if((it->F) < k)
	    break;
	if(p == X && sz(did) == 1)
	    break;
	if(p == X){
	    it = --(--did.end());
	    p = it->S;
	    if((it->F) < k)
		break;
	}
	can[X][p] = 1;
	
	era(p);
	neg(p);
    }
}
void init(int k, vector<int> a){
    n = sz(a);    
    for(int i = 0; i < n; i++){
	a[i] = k-1-a[i];
    }

    set<int> ids;
    set<pii> did;

    build(a);
    auto minim = [&](){
		     return mn[1];
		 };
    auto find = [&](){    
		     return go();
		};
    auto neg = [&](int p){
		   if(p >= k-1)
		       sadd(p-k+1, p+1, -1);
		   else
		       sadd(0, p+1, -1), sadd((p-k+1 + n) % n, n, -1);
	       };
    
    auto add = [&](int p){
		   sadd(p, p+1, inf);
		   if(ids.empty()){
		       ids.insert(p);
		       did.insert({n, p});
		       return;
		   }
		   ids.insert(p);
		   auto it = ids.find(p);
		   auto L = (it == ids.begin() ? --ids.end() : prev(it));
		   auto R = (next(it) == ids.end() ? ids.begin() : next(it));
		   int DIS = ((*R) - (*L) + n) % n;
		   if(DIS == 0)
		       DIS = n;
		   did.erase({DIS, *R});
		   did.insert({((*R) - p + n) % n, *R});
		   did.insert({(p - (*L) + n) % n, p});
	       };
    auto era = [&](int p){
		   if(sz(ids) == 1){
		       ids.clear();
		       did.clear();
		       return;
		   }
		   auto it = ids.find(p);
		   auto L = (it == ids.begin() ? --ids.end() : prev(it));
		   auto R = (next(it) == ids.end() ? ids.begin() : next(it));
		   int DIS = ((*R) - (*L) + n) % n;
		   if(DIS == 0)
		       DIS = n;
		   did.erase({((*R) - p + n) % n, *R});
		   did.erase({(p - (*L) + n) % n, p});
		   did.insert({DIS, *R});
		   ids.erase(p);
	       };
    for(int C = 0; C < n; C++){
	while(minim() == 0)
	    add(find());
	int p = did.rbegin()->S;
	assert((did.rbegin()->F) >= k);
	pos[p] = C;
	era(p);
	neg(p);
    }
    for(int i = 0; i < n; i++)
	again(k, a, i);
}


int compare_plants(int x, int y){
    if(can[x][y] && can[y][x])
	return 0;
    return can[x][y] ? 1 : -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 66 ms 3192 KB Output is correct
7 Runtime error 66 ms 5496 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Execution timed out 4065 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Execution timed out 4065 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 62 ms 5244 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 12 ms 384 KB Output is correct
7 Correct 128 ms 1100 KB Output is correct
8 Correct 61 ms 1016 KB Output is correct
9 Correct 89 ms 1144 KB Output is correct
10 Correct 70 ms 1228 KB Output is correct
11 Correct 123 ms 1080 KB Output is correct
12 Correct 91 ms 1120 KB Output is correct
13 Correct 47 ms 1144 KB Output is correct

Subtask #6
0 / 15.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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Execution timed out 4078 ms 384 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 66 ms 3192 KB Output is correct
7 Runtime error 66 ms 5496 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -