Submission #300965

#	Time	Username	Problem	Language	Result	Execution time	Memory
300965		shayan_p	Comparing Plants (IOI20_plants)	C++17	11 / 100	4078 ms	5496 KiB

plants

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25