oj.uz

Submission #127365

# Submission time Handle Problem Language Result Execution time Memory
127365 2019-07-09T09:23:02 Z JohnTitor Svjetlost (COI18_svjetlost) C++11
100 / 100
 1436 ms 94404 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<<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<<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 504 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 504 KB 93 numbers
5 Correct 5 ms 888 KB 101 numbers
6 Correct 14 ms 1652 KB 1201 numbers
7 Correct 17 ms 1908 KB 1556 numbers
8 Correct 23 ms 2292 KB 1996 numbers
9 Correct 21 ms 2292 KB 1960 numbers
10 Correct 22 ms 2292 KB 1991 numbers
11 Correct 22 ms 2420 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB found '32934.4000000000', expected '32934.3604541195', error '0.0000012007'
2 Correct 6 ms 1004 KB found '31571600.0000000000', expected '31571636.3365447633', error '0.0000011509'
3 Correct 36 ms 5744 KB found '31442600.0000000000', expected '31442617.6286691241', error '0.0000005607'
4 Correct 69 ms 10032 KB found '31424400.0000000000', expected '31424400.0534067489', error '0.0000000017'
5 Correct 277 ms 39700 KB found '3142090000.0000000000', expected '3142086769.6889681816', error '0.0000010281'
6 Correct 280 ms 39840 KB found '3142080000.0000000000', expected '3142076120.8714694977', error '0.0000012346'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2036 KB 1001 numbers
2 Correct 201 ms 18900 KB 15001 numbers
3 Correct 540 ms 45848 KB 44445 numbers
4 Correct 464 ms 49104 KB 22223 numbers
5 Correct 1088 ms 87684 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 504 KB 93 numbers
5 Correct 5 ms 888 KB 101 numbers
6 Correct 14 ms 1652 KB 1201 numbers
7 Correct 17 ms 1908 KB 1556 numbers
8 Correct 23 ms 2292 KB 1996 numbers
9 Correct 21 ms 2292 KB 1960 numbers
10 Correct 22 ms 2292 KB 1991 numbers
11 Correct 22 ms 2420 KB 1963 numbers
12 Correct 2 ms 380 KB found '32934.4000000000', expected '32934.3604541195', error '0.0000012007'
13 Correct 6 ms 1004 KB found '31571600.0000000000', expected '31571636.3365447633', error '0.0000011509'
14 Correct 36 ms 5744 KB found '31442600.0000000000', expected '31442617.6286691241', error '0.0000005607'
15 Correct 69 ms 10032 KB found '31424400.0000000000', expected '31424400.0534067489', error '0.0000000017'
16 Correct 277 ms 39700 KB found '3142090000.0000000000', expected '3142086769.6889681816', error '0.0000010281'
17 Correct 280 ms 39840 KB found '3142080000.0000000000', expected '3142076120.8714694977', error '0.0000012346'
18 Correct 16 ms 2036 KB 1001 numbers
19 Correct 201 ms 18900 KB 15001 numbers
20 Correct 540 ms 45848 KB 44445 numbers
21 Correct 464 ms 49104 KB 22223 numbers
22 Correct 1088 ms 87684 KB 88889 numbers
23 Correct 1436 ms 94236 KB 98175 numbers
24 Correct 333 ms 25112 KB 25905 numbers
25 Correct 1210 ms 94268 KB 98169 numbers
26 Correct 1123 ms 88112 KB 91845 numbers
27 Correct 1225 ms 94404 KB 98296 numbers
28 Correct 1103 ms 82108 KB 85384 numbers
29 Correct 1104 ms 81948 KB 85317 numbers
30 Correct 1221 ms 94224 KB 98246 numbers
31 Correct 738 ms 62160 KB 50001 numbers