oj.uz

Submission #127362

# Submission time Handle Problem Language Result Execution time Memory
127362 2019-07-09T09:20:57 Z JohnTitor Svjetlost (COI18_svjetlost) C++11
40 / 100
 1132 ms 90868 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=1e16;
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 3 ms 404 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 3 ms 404 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 764 KB 101 numbers
6 Correct 14 ms 1524 KB 1201 numbers
7 Correct 18 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 2292 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.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 1016 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 37 ms 5708 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 65 ms 10372 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 292 ms 41540 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 278 ms 41692 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2008 KB 1001 numbers
2 Correct 208 ms 19596 KB 15001 numbers
3 Correct 575 ms 47340 KB 44445 numbers
4 Correct 474 ms 51028 KB 22223 numbers
5 Incorrect 1132 ms 90868 KB 2217th numbers differ - expected: '1800653174.7576336861', found: '1800630958.3355419636', error = '0.0000123380'

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 404 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 764 KB 101 numbers
6 Correct 14 ms 1524 KB 1201 numbers
7 Correct 18 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 2292 KB 1991 numbers
11 Correct 22 ms 2292 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 37 ms 5708 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 65 ms 10372 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 292 ms 41540 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 278 ms 41692 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 17 ms 2008 KB 1001 numbers
19 Correct 208 ms 19596 KB 15001 numbers
20 Correct 575 ms 47340 KB 44445 numbers
21 Correct 474 ms 51028 KB 22223 numbers
22 Incorrect 1132 ms 90868 KB 2217th numbers differ - expected: '1800653174.7576336861', found: '1800630958.3355419636', error = '0.0000123380'