oj.uz

Submission #221285

# Submission time Handle Problem Language Result Execution time Memory
221285 2020-04-09T20:14:18 Z VEGAnn Teams (IOI15_teams) C++14
100 / 100
 1842 ms 373708 KB 
//#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <vector>
#include <cstdio>
#include <algorithm>
#include "teams.h"
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
const int M = 200100;
vector<pii> events, vc;
set<int> st[M], setik;
set<int>::iterator ite, net, pre;
int n, f[M];

struct seg_tree{
    seg_tree *l, *r;
    int sm;

    seg_tree(): l(0), r(0), sm(0) {}
    seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}

    void build(int tl, int tr){
        sm = 0;

        if (tl == tr) return;

        int md = (tl + tr) >> 1;

        l = new seg_tree();
        r = new seg_tree();

        l -> build(tl, md);
        r -> build(md + 1, tr);
    }

    void update(int tl, int tr, int ps){
        sm++;

        if (tl == tr) return;

        int md = (tl + tr) >> 1;

        if (ps <= md){
            l = new seg_tree(l);
            l -> update(tl, md, ps);
        } else {
            r = new seg_tree(r);
            r -> update(md + 1, tr, ps);
        }
    }

    int sum(int tl, int tr, int ql, int qr){
        if (ql > qr) return 0;

        if (ql == tl && qr == tr) return sm;

        int md = (tl + tr) >> 1;

        return l -> sum(tl, md, ql, min(qr, md)) + r -> sum(md + 1, tr, max(md + 1, ql), qr);
    }
};

seg_tree *root[N];

void init(int N, int A[], int B[]) {
    n = N;

    for (int i = 0; i < n; i++)
        vc.PB(MP(A[i], B[i]));

    sort(all(vc));

    root[n] = new seg_tree();
    root[n] -> build(1, n);

    for (int i = n - 1; i >= 0; i--){
        root[i] = new seg_tree(root[i + 1]);
        root[i] -> update(1, n, vc[i].sd);
    }
}

int calc(int x1, int y1, int x2, int y2){
    int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
    int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();

    return (root[lf] -> sum(1, n, y1, y2)) - (root[rt] -> sum(1, n, y1, y2));
}

bool better(int i, int j, int k){
    int cr = events[k].ft;
    return (f[i] + calc(events[i].ft + 1, cr, cr, n) <= f[j] + calc(events[j].ft + 1, cr, cr, n));
}

void change(int i, int j, int beg, bool insrt){
    int l = beg, r = sz(events);

    while (l < r){
        int k = (l + r) >> 1;

        if (better(i, j, k))
            r = k;
        else l = k + 1;
    }

     if (l < sz(events)) {
        if (insrt)
            st[l].insert(i);
        else st[l].erase(i);
     }
}

int can(int M, int K[]) {
    sort(K, K + M);

    events.clear();

    ll sum = 0ll;

    for (int i = 0; i < M; ){
        int j = i;
        events.PB(MP(K[i], 0));

        while (j < M && K[i] == K[j]){
            sum += K[j];
            events.back().sd++;
            j++;
        }

        i = j;
    }

    if (sum > ll(n)) return 0;

    setik.clear();
    for (int it = 0; it < sz(events); it++)
        st[it].clear();

    for (int it = 0; it < sz(events); it++){
        pii cr = events[it];

        int cur_kol = cr.ft * cr.sd;

        f[it] = calc(1, cr.ft, cr.ft, n) - cur_kol;

        while (sz(st[it]) > 0){
            int vl = (*(--st[it].end()));
            st[it].erase(--st[it].end());

            ite = setik.find(vl);

            int mem_net = *next(ite);

            setik.erase(next(ite));

            net = next(ite);

            if (net != setik.end()) {
                change(mem_net, *net, it, 0);
                change(vl, *net, it, 1);
            }
        }

        if (sz(setik)) {
            int pr = (*(--setik.end()));
            f[it] = min(f[it], f[pr] + calc(events[pr].ft + 1, cr.ft, cr.ft, n) - cur_kol);
        }

        if (f[it] < 0)
            return 0;

        if (!sz(setik)){
            setik.insert(it);
            continue;
        }

        int lst = (*(--setik.end()));

        if (it + 1 < sz(events) && !better(lst, it, it + 1)){
            change(lst, it, it + 1, 1);
            setik.insert(it);
        }
    }

    return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:75:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:18:11: note: shadowed declaration is here
 const int N = 500100;
           ^
teams.cpp: In function 'int calc(int, int, int, int)':
teams.cpp:93:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
     int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp:94:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
     int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:122:23: warning: declaration of 'M' shadows a global declaration [-Wshadow]
 int can(int M, int K[]) {
                       ^
teams.cpp:19:11: note: shadowed declaration is here
 const int M = 200100;
           ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 9 ms 9856 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct
13 Correct 10 ms 9856 KB Output is correct
14 Correct 10 ms 9728 KB Output is correct
15 Correct 9 ms 9728 KB Output is correct
16 Correct 10 ms 9728 KB Output is correct
17 Correct 9 ms 9728 KB Output is correct
18 Correct 9 ms 9728 KB Output is correct
19 Correct 10 ms 9728 KB Output is correct
20 Correct 10 ms 9728 KB Output is correct
21 Correct 10 ms 9728 KB Output is correct
22 Correct 10 ms 9728 KB Output is correct
23 Correct 10 ms 9728 KB Output is correct
24 Correct 10 ms 9728 KB Output is correct
25 Correct 10 ms 9728 KB Output is correct
26 Correct 10 ms 9728 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 73836 KB Output is correct
2 Correct 125 ms 73708 KB Output is correct
3 Correct 128 ms 73888 KB Output is correct
4 Correct 127 ms 74220 KB Output is correct
5 Correct 90 ms 73836 KB Output is correct
6 Correct 90 ms 73836 KB Output is correct
7 Correct 94 ms 73708 KB Output is correct
8 Correct 91 ms 73732 KB Output is correct
9 Correct 82 ms 71660 KB Output is correct
10 Correct 84 ms 71660 KB Output is correct
11 Correct 85 ms 74732 KB Output is correct
12 Correct 87 ms 71532 KB Output is correct
13 Correct 102 ms 74604 KB Output is correct
14 Correct 96 ms 72300 KB Output is correct
15 Correct 116 ms 73708 KB Output is correct
16 Correct 120 ms 73708 KB Output is correct
17 Correct 98 ms 74604 KB Output is correct
18 Correct 94 ms 74604 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 74092 KB Output is correct
2 Correct 134 ms 74092 KB Output is correct
3 Correct 286 ms 77164 KB Output is correct
4 Correct 123 ms 74092 KB Output is correct
5 Correct 226 ms 74220 KB Output is correct
6 Correct 208 ms 74196 KB Output is correct
7 Correct 100 ms 74244 KB Output is correct
8 Correct 183 ms 74092 KB Output is correct
9 Correct 82 ms 71660 KB Output is correct
10 Correct 87 ms 71960 KB Output is correct
11 Correct 115 ms 75092 KB Output is correct
12 Correct 535 ms 72044 KB Output is correct
13 Correct 519 ms 75116 KB Output is correct
14 Correct 329 ms 75372 KB Output is correct
15 Correct 349 ms 74220 KB Output is correct
16 Correct 338 ms 74220 KB Output is correct
17 Correct 258 ms 75116 KB Output is correct
18 Correct 301 ms 75116 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 366040 KB Output is correct
2 Correct 765 ms 365964 KB Output is correct
3 Correct 1248 ms 371932 KB Output is correct
4 Correct 750 ms 366048 KB Output is correct
5 Correct 779 ms 366048 KB Output is correct
6 Correct 741 ms 366048 KB Output is correct
7 Correct 477 ms 365920 KB Output is correct
8 Correct 691 ms 365908 KB Output is correct
9 Correct 408 ms 350944 KB Output is correct
10 Correct 438 ms 366736 KB Output is correct
11 Correct 735 ms 366844 KB Output is correct
12 Correct 1601 ms 366952 KB Output is correct
13 Correct 1842 ms 366688 KB Output is correct
14 Correct 1359 ms 367328 KB Output is correct
15 Correct 1265 ms 373708 KB Output is correct
16 Correct 1219 ms 373588 KB Output is correct
17 Correct 989 ms 373476 KB Output is correct
18 Correct 1004 ms 373504 KB Output is correct