oj.uz

Submission #748756

# Submission time Handle Problem Language Result Execution time Memory
748756 2023-05-26T23:47:39 Z Username4132 Svjetlost (COI18_svjetlost) C++14
40 / 100
 165 ms 12336 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){
    ld x=p.F, y=p.S;
    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 'int main()':
svjetlost.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:96:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:115:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         int v; scanf("%d", &v); --v;
      |                ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB 11 numbers
2 Correct 1 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 0 ms 340 KB 11 numbers
2 Correct 1 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 724 KB 1996 numbers
9 Correct 6 ms 796 KB 1960 numbers
10 Correct 7 ms 724 KB 1991 numbers
11 Correct 7 ms 724 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1876 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 17 ms 2840 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 70 ms 10724 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 72 ms 10760 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 63 ms 4928 KB 15001 numbers
3 Correct 165 ms 11224 KB 44445 numbers
4 Incorrect 121 ms 12336 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 0 ms 340 KB 11 numbers
2 Correct 1 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 724 KB 1996 numbers
9 Correct 6 ms 796 KB 1960 numbers
10 Correct 7 ms 724 KB 1991 numbers
11 Correct 7 ms 724 KB 1963 numbers
12 Correct 0 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 1876 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 17 ms 2840 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 70 ms 10724 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 72 ms 10760 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 5 ms 724 KB 1001 numbers
19 Correct 63 ms 4928 KB 15001 numbers
20 Correct 165 ms 11224 KB 44445 numbers
21 Incorrect 121 ms 12336 KB Expected double, but "-nan" found
22 Halted 0 ms 0 KB -