oj.uz

Submission #127363

# Submission time Handle Problem Language Result Execution time Memory
127363 2019-07-09T09:21:36 Z JohnTitor Svjetlost (COI18_svjetlost) C++11
100 / 100
 1493 ms 97716 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);
    cout<<setprecision(6)<<fixed<<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(6)<<fixed<<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 3 ms 376 KB 41 numbers
3 Correct 3 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 3 ms 376 KB 41 numbers
3 Correct 3 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 6 ms 888 KB 101 numbers
6 Correct 14 ms 1524 KB 1201 numbers
7 Correct 19 ms 1908 KB 1556 numbers
8 Correct 23 ms 2292 KB 1996 numbers
9 Correct 22 ms 2164 KB 1960 numbers
10 Correct 23 ms 2292 KB 1991 numbers
11 Correct 22 ms 2164 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 1016 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 35 ms 5684 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 64 ms 10076 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 291 ms 39860 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 301 ms 39896 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2036 KB 1001 numbers
2 Correct 205 ms 19008 KB 15001 numbers
3 Correct 560 ms 45912 KB 44445 numbers
4 Correct 477 ms 49228 KB 22223 numbers
5 Correct 1127 ms 88220 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 3 ms 376 KB 41 numbers
3 Correct 3 ms 376 KB 11 numbers
4 Correct 3 ms 376 KB 93 numbers
5 Correct 6 ms 888 KB 101 numbers
6 Correct 14 ms 1524 KB 1201 numbers
7 Correct 19 ms 1908 KB 1556 numbers
8 Correct 23 ms 2292 KB 1996 numbers
9 Correct 22 ms 2164 KB 1960 numbers
10 Correct 23 ms 2292 KB 1991 numbers
11 Correct 22 ms 2164 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 6 ms 1016 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 35 ms 5684 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 64 ms 10076 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 291 ms 39860 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 301 ms 39896 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 17 ms 2036 KB 1001 numbers
19 Correct 205 ms 19008 KB 15001 numbers
20 Correct 560 ms 45912 KB 44445 numbers
21 Correct 477 ms 49228 KB 22223 numbers
22 Correct 1127 ms 88220 KB 88889 numbers
23 Correct 1493 ms 97644 KB 98175 numbers
24 Correct 345 ms 25872 KB 25905 numbers
25 Correct 1275 ms 97716 KB 98169 numbers
26 Correct 1200 ms 91156 KB 91845 numbers
27 Correct 1303 ms 97640 KB 98296 numbers
28 Correct 1172 ms 85060 KB 85384 numbers
29 Correct 1113 ms 84888 KB 85317 numbers
30 Correct 1263 ms 97660 KB 98246 numbers
31 Correct 716 ms 64444 KB 50001 numbers