Submission #221285

#	Time	Username	Problem	Language	Result	Execution time	Memory
221285		VEGAnn	Teams (IOI15_teams)	C++14	100 / 100	1842 ms	373708 KiB

teams

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

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23