oj.uz

Submission #748757

# Submission time Handle Problem Language Result Execution time Memory
748757 2023-05-26T23:49:55 Z Username4132 Svjetlost (COI18_svjetlost) C++14
40 / 100
 168 ms 12300 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[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;
    assert(ret>=0);
    return sqrtl(ret);
}

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:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:98:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:117:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         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 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 1 ms 340 KB 41 numbers
3 Correct 1 ms 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers
5 Correct 2 ms 468 KB 101 numbers
6 Correct 6 ms 596 KB 1201 numbers
7 Correct 6 ms 724 KB 1556 numbers
8 Correct 6 ms 724 KB 1996 numbers
9 Correct 6 ms 724 KB 1960 numbers
10 Correct 7 ms 808 KB 1991 numbers
11 Correct 6 ms 804 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 1 ms 480 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 9 ms 1748 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 19 ms 2920 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 75 ms 10700 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 72 ms 10744 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB 1001 numbers
2 Correct 61 ms 4920 KB 15001 numbers
3 Correct 168 ms 11152 KB 44445 numbers
4 Incorrect 127 ms 12300 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 340 KB 11 numbers
4 Correct 1 ms 340 KB 93 numbers
5 Correct 2 ms 468 KB 101 numbers
6 Correct 6 ms 596 KB 1201 numbers
7 Correct 6 ms 724 KB 1556 numbers
8 Correct 6 ms 724 KB 1996 numbers
9 Correct 6 ms 724 KB 1960 numbers
10 Correct 7 ms 808 KB 1991 numbers
11 Correct 6 ms 804 KB 1963 numbers
12 Correct 1 ms 340 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
13 Correct 1 ms 480 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 9 ms 1748 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 19 ms 2920 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 75 ms 10700 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 72 ms 10744 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 4 ms 724 KB 1001 numbers
19 Correct 61 ms 4920 KB 15001 numbers
20 Correct 168 ms 11152 KB 44445 numbers
21 Incorrect 127 ms 12300 KB Expected double, but "-nan" found
22 Halted 0 ms 0 KB -