oj.uz

Submission #127367

# Submission time Handle Problem Language Result Execution time Memory
127367 2019-07-09T09:25:30 Z JohnTitor Svjetlost (COI18_svjetlost) C++11
100 / 100
 1511 ms 95036 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
template <typename CT, typename T> inline void reset_container(CT &c, int sz, T v){c.resize(sz); for(auto &x: c) x=v;}
#define taskname "Svjetlost"
int n;
ld shifted3=((ld)(rng()%10000));
ld shifted2=((ld)(rng()%10000));
ld shifted=((ld)(rng()%100000))/100000;
class point{
public:
    ld x, y;
    void input(){
        read(x);
        read(y);
        ///(x+yi)*(cos(theta)+sin(theta)i);
        ///x=xcos-ysin
        ///y=xsin+ycos
        x+=shifted2;
        y+=shifted3;
        ld nx=x*cos(shifted)-y*sin(shifted);
        ld ny=x*sin(shifted)+y*cos(shifted);
        x=nx;
        y=ny;
//        cerr<<x<<' '<<y<<'\n';
    }
} p[100001];
class node{
public:
    using pointer=node*;
    int id;
    pointer next, prev;
};
node nd[100001];
int k[100001];

ld r=1e20;
class line{
public:
    ld a, b, c;
    line(point A, point B){
        a=A.y-B.y;
        b=B.x-A.x;
        c=-(A.x*a+A.y*b);
    }
    ld when_y_0(){
        return -c/a;
    }
    ld when_x_0(){
        return -c/b;
    }
};
vector <pair <int, pair<int, int>>> queries;
vector <ld> v;
class segment_tree{
public:
    using pointer=segment_tree*;
    ld l, r;
    ld value;
    ld lazy;
    pointer left, right;
    segment_tree(int idl, int idr){
        l=v[idl];
        r=v[idr];
        int idm=(idl+idr)/2;
        value=lazy=0;
        if(idl!=idr){
            left=new segment_tree(idl, idm);
            right=new segment_tree(idm+1, idr);
        }
        else left=right=nullptr;
    }
    void down(){
        left->value+=lazy;
        right->value+=lazy;
        left->lazy+=lazy;
        right->lazy+=lazy;
        lazy=0;
    }
    void update(ld u, ld v, ld x){
        if(l>v||r<u) return;
        else if(u<=l&&v>=r){
            value+=x;
            lazy+=x;
        }
        else{
            down();
            left->update(u, v, x);
            right->update(u, v, x);
            value=max(left->value, right->value);
        }
    }
};
segment_tree::pointer tree;
pair <ld, ld> get_cut(point A, point B){
    line L(A, B);
    ld y0=L.when_x_0();
    ld x0=L.when_y_0();
    ld h=abs(x0)*abs(y0)/(sqrt(x0*x0+y0*y0));
    ld theta=acosl(h/r);
    ld alpha;
    if(x0>0){
        if(y0>0){
            alpha=acos(h/x0);
        }
        else{
            alpha=pi*2-acos(h/x0);
        }
    }
    else{
        if(y0>0){
            alpha=pi-acos(h/-x0);
        }
        else{
            alpha=pi+acos(h/-x0);
        }
    }
    ///alpha+=theta
    ld f=alpha-theta;
    if(f<0) f+=pi*2;
    ld s=alpha+theta;
    if(s>pi*2) s-=pi*2;
    if(A.x*B.y-B.x*A.y<0) swap(f, s);
    return mp(f, s);
}
void fake(int a, int b){
    auto P=get_cut(p[a], p[b]);
    v.pb(P.first);
    v.pb(P.second);
}
void update_range(ld u, ld v, ld w){
    if(u>v){
        tree->update(u, pi*2, w);
        tree->update(0, v, w);
    }
    else{
        tree->update(u, v, w);
    }
}
void update(int a, int b, int w){
    auto P=get_cut(p[a], p[b]);
//    cerr<<a<<' '<<b<<'\n';
//    cerr<<P.first<<' '<<P.second<<'\n';
    update_range(P.first, P.second, sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y))*w);
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    FOR(i, 1, n) p[i].input();
    int q;
    read(q);
    FOR(i, 1, n){
        nd[i].id=i;
        nd[i].next=&nd[i%n+1];
        nd[i%n+1].prev=&nd[i];
    }
    FOR(i, 1, q){
        int k;
        read(k);
        int a=nd[k].prev->id;
        int b=nd[k].next->id;
        nd[k].prev->next=nd[k].next;
        nd[k].next->prev=nd[k].prev;
        queries.pb(mp(k, mp(a, b)));
    }
    v.pb(0);
    v.pb(pi*2);
    FOR(i, 1, n) fake(i, i%n+1);
    for(auto q: queries){
        fake(q.second.first, q.first);
        fake(q.first, q.second.second);
        fake(q.second.first, q.second.second);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    tree=new segment_tree(0, v.size()-1);
    FOR(i, 1, n) update(i, i%n+1, 1);
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cout<<setprecision(16)<<tree->value<<'\n';
    for(auto q: queries){
        update(q.second.first, q.first, -1);
        update(q.first, q.second.second, -1);
        update(q.second.first, q.second.second, 1);
        cout<<setprecision(16)<<tree->value<<'\n';
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 5 ms 888 KB 101 numbers
6 Correct 15 ms 1652 KB 1201 numbers
7 Correct 19 ms 1908 KB 1556 numbers
8 Correct 23 ms 2292 KB 1996 numbers
9 Correct 22 ms 2292 KB 1960 numbers
10 Correct 23 ms 2420 KB 1991 numbers
11 Correct 22 ms 2292 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 1016 KB found '31571636.3365447707', expected '31571636.3365447633', error '0.0000000000'
3 Correct 35 ms 5764 KB found '31442617.6286691204', expected '31442617.6286691241', error '0.0000000000'
4 Correct 68 ms 10088 KB found '31424400.0534066185', expected '31424400.0534067489', error '0.0000000000'
5 Correct 277 ms 39764 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 287 ms 40028 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2036 KB 1001 numbers
2 Correct 206 ms 18952 KB 15001 numbers
3 Correct 577 ms 45924 KB 44445 numbers
4 Correct 473 ms 49292 KB 22223 numbers
5 Correct 1158 ms 88216 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 5 ms 888 KB 101 numbers
6 Correct 15 ms 1652 KB 1201 numbers
7 Correct 19 ms 1908 KB 1556 numbers
8 Correct 23 ms 2292 KB 1996 numbers
9 Correct 22 ms 2292 KB 1960 numbers
10 Correct 23 ms 2420 KB 1991 numbers
11 Correct 22 ms 2292 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 6 ms 1016 KB found '31571636.3365447707', expected '31571636.3365447633', error '0.0000000000'
14 Correct 35 ms 5764 KB found '31442617.6286691204', expected '31442617.6286691241', error '0.0000000000'
15 Correct 68 ms 10088 KB found '31424400.0534066185', expected '31424400.0534067489', error '0.0000000000'
16 Correct 277 ms 39764 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 287 ms 40028 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 16 ms 2036 KB 1001 numbers
19 Correct 206 ms 18952 KB 15001 numbers
20 Correct 577 ms 45924 KB 44445 numbers
21 Correct 473 ms 49292 KB 22223 numbers
22 Correct 1158 ms 88216 KB 88889 numbers
23 Correct 1511 ms 94880 KB 98175 numbers
24 Correct 356 ms 25280 KB 25905 numbers
25 Correct 1309 ms 94932 KB 98169 numbers
26 Correct 1178 ms 88828 KB 91845 numbers
27 Correct 1296 ms 95036 KB 98296 numbers
28 Correct 1203 ms 82736 KB 85384 numbers
29 Correct 1110 ms 82584 KB 85317 numbers
30 Correct 1263 ms 94936 KB 98246 numbers
31 Correct 723 ms 62552 KB 50001 numbers