oj.uz

Submission #254816

# Submission time Handle Problem Language Result Execution time Memory
254816 2020-07-30T16:09:48 Z Mercenary Svjetlost (COI18_svjetlost) C++14
100 / 100
 1731 ms 108640 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

ii operator - (const ii x , const ii y){
    return mp(x.first - y.first , x.second - y.second);
}

ll operator * (const ii x , const ii y){
    return (ll)x.first * y.second - (ll)x.second * y.first;
}

bool cmp(ii a, ii b){
	if((a < mp(0,0)) != (b < mp(0,0)))return (a < mp(0,0)) < (b < mp(0,0));
	return a * b > 0;
}
bool is_equal(ii a , ii b){
    return !cmp(a,b) && !cmp(b,a);
}
vector<ii> val;

ii a[maxn];
int n , m;
int b[maxn];
int nxt[maxn] , pre[maxn];
struct seg{
    vector<ld> s,lz;
    int n;
    void init(int _n){
        n = _n;
        s.resize((n+5) * 4 , 0);
        lz.resize((n+5) * 4 , 0);
    }
    void push(int x , bool key){
        s[x] += lz[x];
        if(key){
            lz[x * 2] += lz[x];
            lz[x * 2 + 1] += lz[x];
        }
        lz[x] = 0;
    }
    void update(int x , int l , int r , int L , int R , ld delta){
        push(x,l!=r);
        if(L > r || l > R)return;
        if(L <= l && r <= R){
            lz[x] += delta;
            push(x,l!=r);
            return;
        }
        int mid = l + r >> 1;
        update(x * 2 , l , mid , L , R ,delta);
        update(x * 2 + 1 , mid + 1 , r , L , R , delta);
        s[x] = max(s[x * 2] , s[x * 2 + 1]);
    }
    void update(int L , int R , ld delta){
        update(1,1,n,L,R,delta);
    }
}s;
ld dis(ii a , ii b){
    return sqrt((ld)(a.first - b.first) * (a.first - b.first) + (ld)(a.second - b.second) * (a.second - b.second));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i].first >> a[i].second;
        nxt[i] = (i + 1 + n) % n;
        pre[i] = (i - 1 + n) % n;
    }
    for(int i = 0 ; i < n ; ++i){
        val.pb(a[nxt[i]]-a[i]);val.pb(a[i]-a[nxt[i]]);
    }
    cin >> m;
    for(int i = 0 ; i < m ; ++i){
        cin >> b[i];--b[i];
        int u = b[i];
        val.pb(a[nxt[u]]-a[pre[u]]);
        val.pb(a[pre[u]]-a[nxt[u]]);
        pre[nxt[u]] = pre[u];
        nxt[pre[u]] = nxt[u];
    }
    val.pb(mp(0,-1));
    sort(val.begin(),val.end(),cmp);
//    for(auto c : val)cout << c.first << " " << c.second << endl;
    val.erase(unique(val.begin(),val.end(),is_equal) , val.end());
    s.init(2 * val.size());
    auto add = [&](ii a , ii b,ld delta){
        int l = lower_bound(val.begin(),val.end(),a,cmp) - val.begin() + 1;
        int r = lower_bound(val.begin(),val.end(),b,cmp) - val.begin() + 1;
        assert(is_equal(val[l - 1],a));
//        cout << a.first << " " << a.second << " " << l - 1 << endl;
        swap(l,r);
        if(l <= r){
            s.update(2 * l + 1, 2 * r-1,delta);
        }else{
            s.update(2 * l + 1, 2 * val.size(),delta);
            s.update(1 , 2 * r - 1 ,delta);
        }
    };
    for(int i = 0 ; i < n ; ++i){
        nxt[i] = (i + 1 + n) % n;
        pre[i] = (i - 1 + n) % n;
        add(a[nxt[i]]-a[i],a[i]-a[nxt[i]],dis(a[i],a[nxt[i]]));
    }
    cout << fixed << setprecision(6);
    cout << s.s[1] << '\n';
    for(int i = 0 ; i < m ; ++i){
        int u = b[i];
        add(a[nxt[u]]-a[u] , a[u] - a[nxt[u]] , -dis(a[u],a[nxt[u]]));
        add(a[u]-a[pre[u]] , a[pre[u]] - a[u] , -dis(a[u],a[pre[u]]));
        add(a[nxt[u]]-a[pre[u]] , a[pre[u]] - a[nxt[u]] , dis(a[pre[u]],a[nxt[u]]));
        pre[nxt[u]] = pre[u];
        nxt[pre[u]] = nxt[u];
        cout << s.s[1] << '\n';
    }
}

Compilation message

svjetlost.cpp: In member function 'void seg::update(int, int, int, int, int, ld)':
svjetlost.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:81:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:82:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB 11 numbers
2 Correct 1 ms 384 KB 41 numbers
3 Correct 1 ms 384 KB 11 numbers
4 Correct 1 ms 512 KB 93 numbers
5 Correct 3 ms 1024 KB 101 numbers
6 Correct 12 ms 1820 KB 1201 numbers
7 Correct 16 ms 2176 KB 1556 numbers
8 Correct 20 ms 2688 KB 1996 numbers
9 Correct 20 ms 2560 KB 1960 numbers
10 Correct 21 ms 2688 KB 1991 numbers
11 Correct 19 ms 2560 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 4 ms 1152 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 34 ms 6784 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 59 ms 12028 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 265 ms 47848 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 273 ms 47848 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2304 KB 1001 numbers
2 Correct 195 ms 22000 KB 15001 numbers
3 Correct 551 ms 52680 KB 44445 numbers
4 Correct 486 ms 57884 KB 22223 numbers
5 Correct 1113 ms 100996 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB 11 numbers
2 Correct 1 ms 384 KB 41 numbers
3 Correct 1 ms 384 KB 11 numbers
4 Correct 1 ms 512 KB 93 numbers
5 Correct 3 ms 1024 KB 101 numbers
6 Correct 12 ms 1820 KB 1201 numbers
7 Correct 16 ms 2176 KB 1556 numbers
8 Correct 20 ms 2688 KB 1996 numbers
9 Correct 20 ms 2560 KB 1960 numbers
10 Correct 21 ms 2688 KB 1991 numbers
11 Correct 19 ms 2560 KB 1963 numbers
12 Correct 1 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 4 ms 1152 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 34 ms 6784 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 59 ms 12028 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 265 ms 47848 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 273 ms 47848 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 13 ms 2304 KB 1001 numbers
19 Correct 195 ms 22000 KB 15001 numbers
20 Correct 551 ms 52680 KB 44445 numbers
21 Correct 486 ms 57884 KB 22223 numbers
22 Correct 1113 ms 100996 KB 88889 numbers
23 Correct 1731 ms 108512 KB 98175 numbers
24 Correct 365 ms 28908 KB 25905 numbers
25 Correct 1317 ms 108532 KB 98169 numbers
26 Correct 1192 ms 101728 KB 91845 numbers
27 Correct 1280 ms 108640 KB 98296 numbers
28 Correct 1269 ms 94464 KB 85384 numbers
29 Correct 1099 ms 94436 KB 85317 numbers
30 Correct 1245 ms 108512 KB 98246 numbers
31 Correct 682 ms 72296 KB 50001 numbers