oj.uz

답안 #232982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232982 2020-05-18T20:57:38 Z shayan_p Svjetlost (COI18_svjetlost) C++14
26 / 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);
}

int SHIT = 0;

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])){
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 2048 KB 93 numbers

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 2048 KB 93 numbers
5 Correct 8 ms 2048 KB 101 numbers
6 Correct 41 ms 2176 KB 1201 numbers
7 Correct 62 ms 2176 KB 1556 numbers
8 Correct 91 ms 2296 KB 1996 numbers
9 Incorrect 65 ms 2296 KB 1341st numbers differ - expected: '35149029.3687862679', found: '59388249.2976623029', error = '0.6896127820'
10 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 12 ms 4480 KB found '31424400.0534064993', expected '31424400.0534067489', error '0.0000000000'
5 Correct 41 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

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 2432 KB 1001 numbers
2 Execution timed out 3066 ms 5912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 2048 KB 93 numbers
5 Correct 8 ms 2048 KB 101 numbers
6 Correct 41 ms 2176 KB 1201 numbers
7 Correct 62 ms 2176 KB 1556 numbers
8 Correct 91 ms 2296 KB 1996 numbers
9 Incorrect 65 ms 2296 KB 1341st numbers differ - expected: '35149029.3687862679', found: '59388249.2976623029', error = '0.6896127820'
10 Halted 0 ms 0 KB -