oj.uz

Submission #563495

# Submission time Handle Problem Language Result Execution time Memory
563495 2022-05-17T10:53:59 Z Yazan_Alattar Svjetlost (COI18_svjetlost) C++14
40 / 100
 777 ms 249784 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 = 400007;
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 6 ms 9684 KB 11 numbers
2 Correct 5 ms 9712 KB 41 numbers
3 Correct 5 ms 9684 KB 11 numbers
4 Correct 5 ms 9812 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB 11 numbers
2 Correct 5 ms 9712 KB 41 numbers
3 Correct 5 ms 9684 KB 11 numbers
4 Correct 5 ms 9812 KB 93 numbers
5 Correct 9 ms 10452 KB 101 numbers
6 Correct 13 ms 11596 KB 1201 numbers
7 Correct 14 ms 11804 KB 1556 numbers
8 Correct 18 ms 12152 KB 1996 numbers
9 Correct 16 ms 12108 KB 1960 numbers
10 Correct 18 ms 12144 KB 1991 numbers
11 Correct 16 ms 12088 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 8 ms 10624 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 22 ms 17288 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 38 ms 23484 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 157 ms 65808 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 156 ms 65740 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11764 KB 1001 numbers
2 Correct 118 ms 39644 KB 15001 numbers
3 Correct 308 ms 76472 KB 44445 numbers
4 Correct 262 ms 72344 KB 22223 numbers
5 Runtime error 777 ms 249784 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB 11 numbers
2 Correct 5 ms 9712 KB 41 numbers
3 Correct 5 ms 9684 KB 11 numbers
4 Correct 5 ms 9812 KB 93 numbers
5 Correct 9 ms 10452 KB 101 numbers
6 Correct 13 ms 11596 KB 1201 numbers
7 Correct 14 ms 11804 KB 1556 numbers
8 Correct 18 ms 12152 KB 1996 numbers
9 Correct 16 ms 12108 KB 1960 numbers
10 Correct 18 ms 12144 KB 1991 numbers
11 Correct 16 ms 12088 KB 1963 numbers
12 Correct 6 ms 9812 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 8 ms 10624 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 22 ms 17288 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 38 ms 23484 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 157 ms 65808 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 156 ms 65740 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 12 ms 11764 KB 1001 numbers
19 Correct 118 ms 39644 KB 15001 numbers
20 Correct 308 ms 76472 KB 44445 numbers
21 Correct 262 ms 72344 KB 22223 numbers
22 Runtime error 777 ms 249784 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -