oj.uz

Submission #232972

# Submission time Handle Problem Language Result Execution time Memory
232972 2020-05-18T19:52:05 Z shayan_p Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 12280 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){
    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 recalc(int befp, int pos, int l = 0, int r = n, int id = 1){    
    if(emp[id])
	return;
    shift(l, r, id);

    if(r-l == 1){
	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(inside(mnl[id], nxt[befp], mnr[id]) && inside(mxl[id], nxt[befp], mxr[id])){
		    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 1920 KB 11 numbers
2 Correct 5 ms 1920 KB 41 numbers
3 Correct 5 ms 1920 KB 11 numbers
4 Correct 6 ms 2048 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1920 KB 11 numbers
2 Correct 5 ms 1920 KB 41 numbers
3 Correct 5 ms 1920 KB 11 numbers
4 Correct 6 ms 2048 KB 93 numbers
5 Correct 14 ms 2048 KB 101 numbers
6 Correct 100 ms 2316 KB 1201 numbers
7 Correct 138 ms 2296 KB 1556 numbers
8 Correct 223 ms 2424 KB 1996 numbers
9 Correct 170 ms 2304 KB 1960 numbers
10 Correct 179 ms 2304 KB 1991 numbers
11 Correct 183 ms 2304 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 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 38 ms 12280 KB found '3142086769.6889934540', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 36 ms 12280 KB found '3142076120.8714604378', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 2432 KB 1001 numbers
2 Execution timed out 3062 ms 5884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1920 KB 11 numbers
2 Correct 5 ms 1920 KB 41 numbers
3 Correct 5 ms 1920 KB 11 numbers
4 Correct 6 ms 2048 KB 93 numbers
5 Correct 14 ms 2048 KB 101 numbers
6 Correct 100 ms 2316 KB 1201 numbers
7 Correct 138 ms 2296 KB 1556 numbers
8 Correct 223 ms 2424 KB 1996 numbers
9 Correct 170 ms 2304 KB 1960 numbers
10 Correct 179 ms 2304 KB 1991 numbers
11 Correct 183 ms 2304 KB 1963 numbers
12 Correct 7 ms 1920 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 38 ms 12280 KB found '3142086769.6889934540', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 36 ms 12280 KB found '3142076120.8714604378', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 203 ms 2432 KB 1001 numbers
19 Execution timed out 3062 ms 5884 KB Time limit exceeded
20 Halted 0 ms 0 KB -