Submission #232985

#	Time	Username	Problem	Language	Result	Execution time	Memory
232985		shayan_p	Svjetlost (COI18_svjetlost)	C++14	26 / 100	3053 ms	12280 KiB

Main

// Never let them see you bleed...

#include<bits/stdc++.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;
typedef pair<ll, ll> pll;
typedef long double ld;

const int maxn = 1e5 + 10, mod = 1e9 + 7;
const ld inf = 1e18;

pll p[maxn];

ll operator * (pll a, pll b){
    return a.F * b.S - a.S * b.F;   
}
ll operator ^ (pll a, pll b){
    return a.F * b.F + a.S * b.S;
}
pll operator + (pll a, pll b){
    return {a.F + b.F, a.S + b.S};
}
pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}

double lnn(pll a, pll b){
    return sqrt((a-b) ^ (a-b));
}

int n;
int nxt[maxn], bef[maxn];

pair<int, ld> iter(int l, int r){
    double len = 0;
    if(r == l)
	r = nxt[r], len+= lnn(p[l], p[r]);
    while(l != r && (p[nxt[l]] - p[l]) * (p[nxt[r]] - p[r]) > 0)
	len+= lnn(p[r], p[nxt[r]]), r = nxt[r];
    return {r, len};
}


ld val[4 * maxn], lz[4 * maxn];
int lzr[4 * maxn], mnr[4 * maxn], mxr[4 * maxn], mnl[4 * maxn], mxl[4 * maxn];
bool emp[4 * maxn];

void shift(int l, int r, int id){
    val[id]+= lz[id];
    if(lzr[id] != -1){
	mnr[id] = mxr[id] = lzr[id];
    }
    if(r-l > 1){
	lz[2*id]+= lz[id];
	lz[2*id+1]+= lz[id];
	if(lzr[id] != -1)
	    lzr[2*id] = lzr[2*id+1] = lzr[id];	
    }
    lz[id] = 0;
    lzr[id] = -1;
}
void merge(int id){
    val[id] = max(val[2*id], val[2*id+1]);
    emp[id] = emp[2*id] && emp[2*id+1];
    if(emp[2*id])
	mnr[id] = mnr[2*id+1], mnl[id] = mnl[2*id+1];
    else
	mnr[id] = mnr[2*id], mnl[id] = mnl[2*id];
    if(emp[2*id+1])
	mxr[id] = mxr[2*id], mxl[id] = mxl[2*id];
    else
	mxr[id] = mxr[2*id+1], mxl[id] = mxl[2*id+1];
}
void off(int pos, int l = 0, int r = n, int id = 1){
    shift(l, r, id);
    if(r-l == 1){
	val[id] = -inf;
	emp[id] = 1;
	return;
    }
    int mid = (l+r) >> 1;
    if(pos < mid)
	off(pos, l, mid, 2*id);
    else
	off(pos, mid, r, 2*id+1);
    merge(id);
}
bool inside(int L, int pos, int R){
    return ((pos-L+n)%n) + ((R-pos+n)%n) == ((R-L+n)%n);
}

void addAll(ld x, int l, int r, int id){
    val[id]+= x;
    //    shift(l, r, id);
    if(r-l == 1)
	return;
    int mid = (l+r) >> 1;
    addAll(x, l, mid, 2*id);
    addAll(x, mid, r, 2*id+1);   
}
void recalc(int befp, int pos, int l = 0, int r = n, int id = 1){    
    if(emp[id])
	return;
    shift(l, r, id);

    bool A = inside(mnl[id], befp, mnr[id]), B = inside(mxl[id], befp, mxr[id]);
    if(r-l == 1 && l == befp){
	auto x = iter(l, mxr[id]);
	val[id]+= x.S - lnn(p[pos], p[bef[pos]]) - lnn(p[pos], p[nxt[pos]]) + lnn(p[bef[pos]], p[nxt[pos]]);
	mxr[id] = mnr[id] = x.F;
	return;
    }
    
    if(r <= befp || befp < l){ // out of seg
	if(!A && !B)
	    return;
	if(A && B){
	    if(mnr[id] == pos && mxr[id] == pos){
		auto x = iter(mnl[id], befp), y = iter(mxl[id], befp);
		if(x.F == y.F){
		    lz[id]+= -lnn(p[pos], p[befp]) + x.S;
		    lzr[id] = x.F;
		    shift(l, r, id);
		    return;
		}
	    }
	    else if(mnr[id] == befp && mxr[id] == befp){
		auto x = iter(mnl[id], befp), y = iter(mxl[id], befp);
		if(x.F == y.F){
		    lz[id]+= x.S;
		    lzr[id] = x.F;
		    shift(l, r, id);		
		    return;
		}
	    }
	    else if(mnl[id] != nxt[befp] && inside(mnl[id], nxt[befp], mnr[id]) && inside(mxl[id], nxt[befp], mxr[id])){
		assert(lz[id] == 0 && lzr[id] == -1);
		addAll(-lnn(p[pos], p[bef[pos]]) - lnn(p[pos], p[nxt[pos]]) + lnn(p[bef[pos]], p[nxt[pos]]), l, r, id);
		return;
		lz[id]+= -lnn(p[pos], p[bef[pos]]) - lnn(p[pos], p[nxt[pos]]) + lnn(p[bef[pos]], p[nxt[pos]]);
		shift(l, r, id);
		return;
	    }
	}
    }
    int mid = (l+r) >> 1;
    recalc(befp, pos, l, mid, 2*id);
    recalc(befp, pos, mid, r, 2*id+1);
    merge(id);
}
void build(int l = 0, int r = n, int id = 1){
    static int R = 0;
    static ld len = 0;
    if(r-l == 1){
	auto y = iter(l, R);	
	len+= y.S;
	R = y.F;
	mnl[id] = mxl[id] = l;
	mnr[id] = mxr[id] = R;
	val[id] = len;
	len-= lnn(p[l], p[nxt[l]]);
	return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, 2*id);
    build(mid, r, 2*id+1);    
    merge(id);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    memset(lzr, -1, sizeof lzr);
    
    cin >> n;
    for(int i = 0; i < n; i++){
	cin >> p[i].F >> p[i].S;
	nxt[i] = (i+1) % n;
	bef[i] = (i+n-1) % n;
    }    
    build();
    cout << setprecision(7) << fixed << val[1]+lz[1] << "\n";    
    int q;
    cin >> q;
    while(q--){
	int pos;
	cin >> pos;
	--pos;
	int L = bef[pos], R = nxt[pos];	
	bef[R] = L, nxt[L] = R;
	off(pos);
	recalc(L, pos);
	cout << setprecision(7) << fixed << val[1]+lz[1] << "\n";
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31