oj.uz

Submission #748758

# Submission time Handle Problem Language Result Execution time Memory
748758 2023-05-27T00:17:17 Z Username4132 Svjetlost (COI18_svjetlost) C++14
100 / 100
 484 ms 25480 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct node{
    int vind, eind;
    node *pr, *nxt;
    node(int VI=0, int EI=0, node* PR=NULL, node* NX=NULL) : vind(VI), eind(EI), pr(PR), nxt(NX) {}
};

bool up(pii p){
    return p.S>0 || (p.S==0 && p.F>0);
}

bool covers(pii p, pii q){
    return ((ll)p.F)*q.S > ((ll)p.S)*q.F;
}

const int MAXN=100010;
int n, he, u, q, assi[2*MAXN], fin[2*MAXN];
pii pt[MAXN];
node* pol = new node;
node* ver[MAXN];
vector<int> del;
pii edge[2*MAXN];
pair<pii, int> lis[2*MAXN];
ld tr[4*MAXN], lazy[2*MAXN];
bool modif[2*MAXN];


void apply(int p, ld value){
    if(p<u) lazy[p]+=value, modif[p]=true;
    tr[p]+=value;
}

void push(int p){
    for(int s=he; s>0; --s){
        int i=p>>s;
        if(modif[i]){
            apply(i<<1, lazy[i]);
            apply(i<<1|1, lazy[i]);
            lazy[i]=0, modif[i]=false;
        }
    }
}

void build(int p){
    for(; p>1; p>>=1) tr[p>>1] = max(tr[p], tr[p^1]) + lazy[p>>1];
}

void inc(int l, int r, ld value){
    l+=u, r+=u;
    int l0=l, r0=r;
    for(; l<r; l>>=1, r>>=1){
        if(l&1) apply(l++, value);
        if(r&1) apply(--r, value);
    }
    build(l0);
    build(r0-1);
}

void circ_inc(int l, int r, ld value){
    if(l<r) inc(l, r, value);
    else inc(l, u, value), inc(0, r, value);
}

ld query(int l, int r){
    l+=u, r+=u;
    push(l);
    push(r-1);
    ld ret=0;
    for(; l<r; l>>=1, r>>=1){
        if(l&1) ret=max(tr[l++], ret);
        if(r&1) ret=max(tr[--r], ret);
    }
    return ret;
}

ld len(pii p){
    ld x=p.F, y=p.S, ret=x*x+y*y;
    return sqrtl(x*x + y*y);
}

int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
    node* cur=pol;
    forn(i, n-1){
        cur->nxt = new node(i+1, i+1, cur);
        cur=cur->nxt;
    }
    cur->nxt=pol;
    pol->pr=cur;

    node* tmp=pol;
    while(true){
        ver[tmp->vind]=tmp;
        tmp=tmp->nxt;
        if(tmp==pol) break;
    }
    forn(i, n) edge[i]={pt[(i+1)%n].F - pt[i].F, pt[(i+1)%n].S - pt[i].S};
    scanf("%d", &q);
    int ecn=n;
    forn(i, q){
        int v; scanf("%d", &v); --v;
        node *pr = ver[v]->pr, *nxt = ver[v]->nxt;
        
        del.PB(pr->eind), del.PB(ver[v]->eind);
        pii src = pt[pr->vind], dst = pt[nxt->vind];
        edge[ecn] = make_pair(dst.F - src.F, dst.S - src.S);
        pr->nxt=nxt, nxt->pr=pr;
        pr->eind=ecn++;
    }

    forn(i, n+q) lis[i]={edge[i], i};
    sort(lis, lis+n+q, [](pair<pii, int> a, pair<pii, int> b){
        return up(a.F)==up(b.F)? ((ll)a.F.S)*b.F.F < ((ll)a.F.F)*b.F.S : up(a.F)>up(b.F);
    });

    u = n+q;
    he = 8*sizeof(int) - __builtin_clz(u);
    forn(i, u) assi[lis[i].S]=i;
    
    int cuur=1;
    forn(i, u){
        while(covers(lis[i].F, lis[cuur].F)) cuur=(cuur+1)%u;
        fin[i]=cuur;
    }

    cout << setprecision(9) << fixed;
    forn(i, n) circ_inc(assi[i], fin[assi[i]], len(edge[i]));
    cout << query(0, u) << "\n";
    forn(i, q){
        int i1=del[i<<1], i2=del[i<<1|1];
        circ_inc(assi[i1], fin[assi[i1]], -len(edge[i1]));
        circ_inc(assi[i2], fin[assi[i2]], -len(edge[i2]));
        circ_inc(assi[n+i], fin[assi[n+i]], len(edge[n+i]));
        cout << query(0, u) << "\n";
    }
}

Compilation message

svjetlost.cpp: In function 'ld len(pii)':
svjetlost.cpp:91:22: warning: unused variable 'ret' [-Wunused-variable]
   91 |     ld x=p.F, y=p.S, ret=x*x+y*y;
      |                      ^~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:97:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:116:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         int v; scanf("%d", &v); --v;
      |                ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 0 ms 340 KB 41 numbers
3 Correct 0 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 0 ms 340 KB 41 numbers
3 Correct 0 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers
5 Correct 1 ms 468 KB 101 numbers
6 Correct 4 ms 596 KB 1201 numbers
7 Correct 6 ms 724 KB 1556 numbers
8 Correct 7 ms 784 KB 1996 numbers
9 Correct 7 ms 724 KB 1960 numbers
10 Correct 7 ms 948 KB 1991 numbers
11 Correct 9 ms 724 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 468 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 9 ms 1684 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 17 ms 2920 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 69 ms 10752 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 89 ms 10764 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB 1001 numbers
2 Correct 63 ms 4944 KB 15001 numbers
3 Correct 162 ms 11172 KB 44445 numbers
4 Correct 136 ms 12784 KB 22223 numbers
5 Correct 362 ms 23800 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 0 ms 340 KB 41 numbers
3 Correct 0 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers
5 Correct 1 ms 468 KB 101 numbers
6 Correct 4 ms 596 KB 1201 numbers
7 Correct 6 ms 724 KB 1556 numbers
8 Correct 7 ms 784 KB 1996 numbers
9 Correct 7 ms 724 KB 1960 numbers
10 Correct 7 ms 948 KB 1991 numbers
11 Correct 9 ms 724 KB 1963 numbers
12 Correct 1 ms 340 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 468 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 9 ms 1684 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 17 ms 2920 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 69 ms 10752 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 89 ms 10764 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 5 ms 724 KB 1001 numbers
19 Correct 63 ms 4944 KB 15001 numbers
20 Correct 162 ms 11172 KB 44445 numbers
21 Correct 136 ms 12784 KB 22223 numbers
22 Correct 362 ms 23800 KB 88889 numbers
23 Correct 484 ms 25460 KB 98175 numbers
24 Correct 99 ms 6856 KB 25905 numbers
25 Correct 377 ms 25336 KB 98169 numbers
26 Correct 371 ms 23792 KB 91845 numbers
27 Correct 405 ms 25480 KB 98296 numbers
28 Correct 366 ms 22196 KB 85384 numbers
29 Correct 338 ms 22152 KB 85317 numbers
30 Correct 411 ms 25444 KB 98246 numbers
31 Correct 245 ms 17468 KB 50001 numbers