oj.uz

Submission #563496

# Submission time Handle Problem Language Result Execution time Memory
563496 2022-05-17T10:54:31 Z Yazan_Alattar Svjetlost (COI18_svjetlost) C++14
100 / 100
 903 ms 161288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1000007;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

struct Point{
    ll x, y;

    void read(){
        scanf("%lld%lld", &x, &y);
        return;
    }

    Point operator -(const Point &b) const{
        return {x - b.x, y - b.y};
    }

    bool operator <(const Point &b) const{
        bool ok1 = (x < 0 || (x == 0 && y < 0));
        bool ok2 = (b.x < 0 || (b.x == 0 && b.y < 0));

        if(ok1 != ok2) return ok1 < ok2;
        return x * b.y - y * b.x > 0;
    }
};

struct item1{
    Point r, l;
    ll time;
    long double cost;
};

struct item2{
    ll l, r;
    long double cost;
};

bool cmp (Point a, Point b){
    return !(a < b) && !(b < a);
}

// ===========

Point p[M];
vector <Point> tmp;
vector <item1> v;
vector <item2> add[M];
set <int> s;
ll n, q;
long double seg[4 * M], lazy[4 * M];

// ===========

long double dist(Point i, Point j){
    Point ret = i - j;
    return sqrt(ret.x * ret.x + ret.y * ret.y);
}

void upd(int st, int en, long double cost, int node = 1, int l = 1, int r = 2 * tmp.size()){
    if(l > en || r < st) return;
    if(l >= st && r <= en){
        lazy[node] += cost;
        seg[node] += cost;
        return;
    }
    int mid = (l + r) / 2;
    upd(st, en, cost, 2 * node, l, mid);
    upd(st, en, cost, 2 * node + 1, mid + 1, r);
    seg[node] = max(seg[2 * node], seg[2 * node + 1]) + lazy[node];
    return;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) p[i].read();
    p[n + 1] = p[1];

    for(int i = 1; i <= n; ++i){
        s.insert(i);
        v.pb({p[i + 1] - p[i], p[i] - p[i + 1], 0, dist(p[i], p[i + 1])});
    }

    scanf("%d", &q);
    for(int i = 1; i <= q; ++i){
        int x, l, r;
        scanf("%d", &x);

        s.erase(x);

        auto ptr = s.upper_bound(x);
        if(ptr == s.end()) ptr = s.begin();
        r = *ptr;

        ptr = s.lower_bound(x);
        if(ptr == s.begin()) ptr = s.end();
        l = *(--ptr);

        v.pb({p[x] - p[l], p[l] - p[x], i, -dist(p[l], p[x])});
        v.pb({p[r] - p[x], p[x] - p[r], i, -dist(p[x], p[r])});
        v.pb({p[r] - p[l], p[l] - p[r], i, dist(p[l], p[r])});
    }

    tmp.pb({0, -1});
    for(auto i : v){
        tmp.pb(i.l);
        tmp.pb(i.r);
    }

    sort(all(tmp));
    tmp.erase(unique(all(tmp), cmp), tmp.end());

    for(auto i : v){
        int j1 = lower_bound(all(tmp), i.l) - tmp.begin() + 1;
        int j2 = lower_bound(all(tmp), i.r) - tmp.begin() + 1;

        if(j1 <= j2) add[i.time].pb({2 * j1 + 1, 2 * j2 - 1, i.cost});
        else{
            add[i.time].pb({2 * j1 + 1, 2 * tmp.size(), i.cost});
            add[i.time].pb({1, 2 * j2 - 1, i.cost});
        }
    }

    for(int i = 0; i <= q; ++i){
        for(auto j : add[i]) upd(j.l, j.r, j.cost);
        printf("%.6Lf\n", seg[1]);
    }
    return 0;
}

Compilation message

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:86:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   86 |     scanf("%d", &n);
      |            ~^   ~~
      |             |   |
      |             |   ll* {aka long long int*}
      |             int*
      |            %lld
svjetlost.cpp:95:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   95 |     scanf("%d", &q);
      |            ~^   ~~
      |             |   |
      |             |   ll* {aka long long int*}
      |             int*
      |            %lld
svjetlost.cpp:130:43: warning: narrowing conversion of '(2 * tmp.std::vector<Point>::size())' from 'std::vector<Point>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
  130 |             add[i.time].pb({2 * j1 + 1, 2 * tmp.size(), i.cost});
      |                                         ~~^~~~~~~~~~~~
svjetlost.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
svjetlost.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
svjetlost.cpp: In member function 'void Point::read()':
svjetlost.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%lld%lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23840 KB 11 numbers
2 Correct 12 ms 23764 KB 41 numbers
3 Correct 12 ms 23800 KB 11 numbers
4 Correct 12 ms 23944 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23840 KB 11 numbers
2 Correct 12 ms 23764 KB 41 numbers
3 Correct 12 ms 23800 KB 11 numbers
4 Correct 12 ms 23944 KB 93 numbers
5 Correct 13 ms 24532 KB 101 numbers
6 Correct 18 ms 25676 KB 1201 numbers
7 Correct 21 ms 25848 KB 1556 numbers
8 Correct 24 ms 26164 KB 1996 numbers
9 Correct 22 ms 26188 KB 1960 numbers
10 Correct 23 ms 26136 KB 1991 numbers
11 Correct 23 ms 26188 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23908 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 14 ms 24660 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 28 ms 31304 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 45 ms 37240 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 160 ms 78024 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 157 ms 78112 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25804 KB 1001 numbers
2 Correct 127 ms 53096 KB 15001 numbers
3 Correct 342 ms 89204 KB 44445 numbers
4 Correct 267 ms 84616 KB 22223 numbers
5 Correct 626 ms 153188 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23840 KB 11 numbers
2 Correct 12 ms 23764 KB 41 numbers
3 Correct 12 ms 23800 KB 11 numbers
4 Correct 12 ms 23944 KB 93 numbers
5 Correct 13 ms 24532 KB 101 numbers
6 Correct 18 ms 25676 KB 1201 numbers
7 Correct 21 ms 25848 KB 1556 numbers
8 Correct 24 ms 26164 KB 1996 numbers
9 Correct 22 ms 26188 KB 1960 numbers
10 Correct 23 ms 26136 KB 1991 numbers
11 Correct 23 ms 26188 KB 1963 numbers
12 Correct 12 ms 23908 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 14 ms 24660 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 28 ms 31304 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 45 ms 37240 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 160 ms 78024 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 157 ms 78112 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 19 ms 25804 KB 1001 numbers
19 Correct 127 ms 53096 KB 15001 numbers
20 Correct 342 ms 89204 KB 44445 numbers
21 Correct 267 ms 84616 KB 22223 numbers
22 Correct 626 ms 153188 KB 88889 numbers
23 Correct 903 ms 160780 KB 98175 numbers
24 Correct 212 ms 58608 KB 25905 numbers
25 Correct 724 ms 160924 KB 98169 numbers
26 Correct 693 ms 159520 KB 91845 numbers
27 Correct 752 ms 161204 KB 98296 numbers
28 Correct 673 ms 148232 KB 85384 numbers
29 Correct 661 ms 148384 KB 85317 numbers
30 Correct 720 ms 161288 KB 98246 numbers
31 Correct 397 ms 99100 KB 50001 numbers