oj.uz

Submission #225241

# Submission time Handle Problem Language Result Execution time Memory
225241 2020-04-19T19:43:08 Z VEGAnn Teams (IOI15_teams) C++14
100 / 100
 1288 ms 371936 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, events[j].ft, n) <= f[j];
}

void change(int i, int j, int beg, bool insrt){
    if (!better(i, j, sz(events) - 1))
        return;

    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:125: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 11 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 9 ms 9856 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 11 ms 9908 KB Output is correct
11 Correct 11 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct
13 Correct 11 ms 9856 KB Output is correct
14 Correct 10 ms 9728 KB Output is correct
15 Correct 10 ms 9728 KB Output is correct
16 Correct 9 ms 9728 KB Output is correct
17 Correct 9 ms 9728 KB Output is correct
18 Correct 10 ms 9728 KB Output is correct
19 Correct 9 ms 9728 KB Output is correct
20 Correct 11 ms 9728 KB Output is correct
21 Correct 10 ms 9728 KB Output is correct
22 Correct 11 ms 9728 KB Output is correct
23 Correct 10 ms 9728 KB Output is correct
24 Correct 9 ms 9728 KB Output is correct
25 Correct 11 ms 9728 KB Output is correct
26 Correct 9 ms 9728 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 73736 KB Output is correct
2 Correct 128 ms 73796 KB Output is correct
3 Correct 123 ms 73708 KB Output is correct
4 Correct 125 ms 74092 KB Output is correct
5 Correct 99 ms 73836 KB Output is correct
6 Correct 98 ms 73812 KB Output is correct
7 Correct 97 ms 73836 KB Output is correct
8 Correct 93 ms 73708 KB Output is correct
9 Correct 89 ms 71788 KB Output is correct
10 Correct 88 ms 71660 KB Output is correct
11 Correct 93 ms 74732 KB Output is correct
12 Correct 90 ms 71532 KB Output is correct
13 Correct 101 ms 74604 KB Output is correct
14 Correct 95 ms 72300 KB Output is correct
15 Correct 116 ms 73836 KB Output is correct
16 Correct 122 ms 73692 KB Output is correct
17 Correct 95 ms 74604 KB Output is correct
18 Correct 100 ms 74736 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 74092 KB Output is correct
2 Correct 157 ms 74092 KB Output is correct
3 Correct 284 ms 77112 KB Output is correct
4 Correct 125 ms 74176 KB Output is correct
5 Correct 189 ms 74320 KB Output is correct
6 Correct 185 ms 74092 KB Output is correct
7 Correct 106 ms 74092 KB Output is correct
8 Correct 163 ms 74220 KB Output is correct
9 Correct 87 ms 71788 KB Output is correct
10 Correct 86 ms 71920 KB Output is correct
11 Correct 100 ms 75116 KB Output is correct
12 Correct 228 ms 72028 KB Output is correct
13 Correct 307 ms 75040 KB Output is correct
14 Correct 317 ms 75372 KB Output is correct
15 Correct 253 ms 74220 KB Output is correct
16 Correct 253 ms 74220 KB Output is correct
17 Correct 202 ms 75116 KB Output is correct
18 Correct 208 ms 75120 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 365920 KB Output is correct
2 Correct 750 ms 365924 KB Output is correct
3 Correct 1224 ms 371936 KB Output is correct
4 Correct 815 ms 365920 KB Output is correct
5 Correct 709 ms 366088 KB Output is correct
6 Correct 694 ms 365920 KB Output is correct
7 Correct 485 ms 366100 KB Output is correct
8 Correct 665 ms 366048 KB Output is correct
9 Correct 429 ms 350944 KB Output is correct
10 Correct 454 ms 366944 KB Output is correct
11 Correct 537 ms 366688 KB Output is correct
12 Correct 811 ms 366812 KB Output is correct
13 Correct 1169 ms 366816 KB Output is correct
14 Correct 1288 ms 367416 KB Output is correct
15 Correct 960 ms 366404 KB Output is correct
16 Correct 980 ms 366560 KB Output is correct
17 Correct 751 ms 366820 KB Output is correct
18 Correct 765 ms 366816 KB Output is correct