Submission #220790

#	Time	Username	Problem	Language	Result	Execution time	Memory
220790		VEGAnn	Teams (IOI15_teams)	C++14	77 / 100	4088 ms	362720 KiB

teams

#include <bits/stdc++.h>
#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 BLOCK = 316;
set<pii> st;
set<pii>::iterator ite;
vector<pii> events, vc;
int n, f[N];

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));
}

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

    if (M < BLOCK) {
        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;

        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;

            for (int pr = 0; pr < it; pr++)
                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;
        }
    } else {
        st.clear();

        int it = 0;

        for (int i = 0; i < M; i++){

            while (it < n && vc[it].ft <= K[i]){
                st.insert(MP(vc[it].sd, it));
                it++;
            }

            for (int j = 0; j < K[i]; j++){
                ite = st.lower_bound(MP(K[i], -oo));

                if (ite == st.end())
                    return 0;

                st.erase(ite);
            }
        }
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:70:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:13:11: note: shadowed declaration is here
 const int N = 500100;
           ^
teams.cpp: In function 'int calc(int, int, int, int)':
teams.cpp:88: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:89: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();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23