oj.uz

Submission #232989

# Submission time Handle Problem Language Result Execution time Memory
232989 2020-05-18T21:41:01 Z shayan_p Svjetlost (COI18_svjetlost) C++14
100 / 100
 1375 ms 21752 KB 
// 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){
    assert(lz[2*id] == 0 && lz[2*id+1] == 0);///////
    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), shift(mid, r, 2*id+1);
    else
	off(pos, mid, r, 2*id+1), shift(l, mid, 2*id);
    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){
    shift(l, r, id);
    if(emp[id])
	return;

    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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB 11 numbers
2 Correct 5 ms 2048 KB 41 numbers
3 Correct 5 ms 1920 KB 11 numbers
4 Correct 6 ms 1920 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB 11 numbers
2 Correct 5 ms 2048 KB 41 numbers
3 Correct 5 ms 1920 KB 11 numbers
4 Correct 6 ms 1920 KB 93 numbers
5 Correct 6 ms 2048 KB 101 numbers
6 Correct 10 ms 2304 KB 1201 numbers
7 Correct 12 ms 2176 KB 1556 numbers
8 Correct 15 ms 2304 KB 1996 numbers
9 Correct 13 ms 2176 KB 1960 numbers
10 Correct 15 ms 2304 KB 1991 numbers
11 Correct 15 ms 2300 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 2176 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
3 Correct 9 ms 3328 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
4 Correct 13 ms 4480 KB found '31424400.0534064993', expected '31424400.0534067489', error '0.0000000000'
5 Correct 41 ms 12288 KB found '3142086769.6889934540', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 38 ms 12280 KB found '3142076120.8714604378', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2432 KB 1001 numbers
2 Correct 94 ms 6008 KB 15001 numbers
3 Correct 267 ms 10232 KB 44445 numbers
4 Correct 174 ms 16888 KB 22223 numbers
5 Correct 541 ms 18428 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB 11 numbers
2 Correct 5 ms 2048 KB 41 numbers
3 Correct 5 ms 1920 KB 11 numbers
4 Correct 6 ms 1920 KB 93 numbers
5 Correct 6 ms 2048 KB 101 numbers
6 Correct 10 ms 2304 KB 1201 numbers
7 Correct 12 ms 2176 KB 1556 numbers
8 Correct 15 ms 2304 KB 1996 numbers
9 Correct 13 ms 2176 KB 1960 numbers
10 Correct 15 ms 2304 KB 1991 numbers
11 Correct 15 ms 2300 KB 1963 numbers
12 Correct 5 ms 2048 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
13 Correct 6 ms 2176 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
14 Correct 9 ms 3328 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
15 Correct 13 ms 4480 KB found '31424400.0534064993', expected '31424400.0534067489', error '0.0000000000'
16 Correct 41 ms 12288 KB found '3142086769.6889934540', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 38 ms 12280 KB found '3142076120.8714604378', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 11 ms 2432 KB 1001 numbers
19 Correct 94 ms 6008 KB 15001 numbers
20 Correct 267 ms 10232 KB 44445 numbers
21 Correct 174 ms 16888 KB 22223 numbers
22 Correct 541 ms 18428 KB 88889 numbers
23 Correct 785 ms 21496 KB 98175 numbers
24 Correct 160 ms 6904 KB 25905 numbers
25 Correct 804 ms 21624 KB 98169 numbers
26 Correct 1375 ms 21244 KB 91845 numbers
27 Correct 964 ms 21752 KB 98296 numbers
28 Correct 535 ms 20628 KB 85384 numbers
29 Correct 548 ms 20600 KB 85317 numbers
30 Correct 950 ms 21524 KB 98246 numbers
31 Correct 339 ms 19448 KB 50001 numbers