Submission #563495

#	Time	Username	Problem	Language	Result	Execution time	Memory
563495		Yazan_Alattar	Svjetlost (COI18_svjetlost)	C++14	40 / 100	777 ms	249784 KiB

Main

#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 (stderr)

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 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31