oj.uz

Submission #748755

# Submission time Handle Problem Language Result Execution time Memory
748755 2023-05-26T23:37:41 Z Username4132 Svjetlost (COI18_svjetlost) C++14
40 / 100
 183 ms 14288 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
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[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){
    return sqrtl(((ll)p.F)*p.F + ((ll)p.S)*p.S);
}

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 'int main()':
svjetlost.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:95:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:114:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         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 1 ms 340 KB 41 numbers
3 Correct 1 ms 328 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 1 ms 340 KB 41 numbers
3 Correct 1 ms 328 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 720 KB 1556 numbers
8 Correct 7 ms 852 KB 1996 numbers
9 Correct 6 ms 852 KB 1960 numbers
10 Correct 7 ms 848 KB 1991 numbers
11 Correct 7 ms 852 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 1744 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 16 ms 3024 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 69 ms 10716 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 71 ms 10768 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB 1001 numbers
2 Correct 62 ms 5580 KB 15001 numbers
3 Correct 183 ms 12644 KB 44445 numbers
4 Incorrect 125 ms 14288 KB Expected double, but "-nan" found
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 11 numbers
2 Correct 1 ms 340 KB 41 numbers
3 Correct 1 ms 328 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 720 KB 1556 numbers
8 Correct 7 ms 852 KB 1996 numbers
9 Correct 6 ms 852 KB 1960 numbers
10 Correct 7 ms 848 KB 1991 numbers
11 Correct 7 ms 852 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 1744 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 16 ms 3024 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 69 ms 10716 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 71 ms 10768 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 5 ms 724 KB 1001 numbers
19 Correct 62 ms 5580 KB 15001 numbers
20 Correct 183 ms 12644 KB 44445 numbers
21 Incorrect 125 ms 14288 KB Expected double, but "-nan" found
22 Halted 0 ms 0 KB -