Submission #748758

#	Time	Username	Problem	Language	Result	Execution time	Memory
748758		Username4132	Svjetlost (COI18_svjetlost)	C++14	100 / 100	484 ms	25480 KiB

Main

#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 (stderr)

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 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31