Submission #220768

#	Time	Username	Problem	Language	Result	Execution time	Memory
220768		VEGAnn	Teams (IOI15_teams)	C++14	0 / 100	597 ms	129892 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;
vector<int> lf, rt;
vector<pii> vc, events;
int n, kol, tt = 0;
ll mx[4 * N], psh[4 * N]; // constraints here can be smaller

struct seg_tree{
    vector<int> ys;

    seg_tree(): ys(0) {}
};

seg_tree st[4 * N];

void build(int v, int l, int r){
    if (l == r){
        st[v].ys.clear();
        st[v].ys.PB(vc[l].sd);
        return;
    }

    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    merge(all(st[v + v].ys), all(st[v + v + 1].ys), back_inserter(st[v].ys));
}

int calc(int v, int l, int r, int min_x, int max_y){
    if (vc[r].ft < min_x) return 0;

    if (vc[l].ft >= min_x){
        int kol = upper_bound(all(st[v].ys), max_y) - st[v].ys.begin();
        return kol;
    }

    int md = (l + r) >> 1;

    return calc(v + v, l, md, min_x, max_y) + calc(v + v + 1, md + 1, r, min_x, max_y);
}

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

    vc.clear();

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

    sort(all(vc));
    sort(all(lf));
    sort(all(rt));

    build(1, 0, n - 1);
}

void new_build(int v, int l, int r){
    mx[v] = 0;
    psh[v] = 0;

    if (l == r) return;

    int md = (l + r) >> 1;
    new_build(v + v, l, md);
    new_build(v + v + 1, md + 1, r);
}

void push(int v){
    if (psh[v] != 0){
        mx[v] += psh[v];

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }

        psh[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, ll vl){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r) {
        psh[v] = vl;
        push(v);
        return;
    }

    int md = (tl + tr) >> 1;
    update(v + v, tl, md, l, min(r, md), vl);
    update(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    mx[v] = max(mx[v + v], mx[v + v + 1]);
}

int can(int M, int K[]) {

    sort(K, K + M);
    tt++;

    events.clear();

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

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

        i = j;
    }

    new_build(1, 0, sz(events) - 1);

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

        if (it > 0){
            if (events[it - 1].ft + 1 <= events[it].ft - 1){
                int kol = calc(1, 0, n - 1, events[it - 1].ft + 1, events[it].ft - 1);
                update(1, 0, sz(events) - 1, 0, it - 1, kol);
            }
        }

        int kol_up = n - (upper_bound(all(lf), events[it].ft) - lf.begin());
        int kol_lo = lower_bound(all(rt), events[it].ft) - rt.begin();

        update(1, 0, sz(events) - 1, it, it, kol_lo);
        update(1, 0, sz(events) - 1, 0, it, ll(cr.sd) * ll(cr.ft));

        if (mx[1] + ll(kol_up) > ll(n))
            return 0;
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int calc(int, int, int, int, int)':
teams.cpp:45:13: warning: declaration of 'kol' shadows a global declaration [-Wshadow]
         int kol = upper_bound(all(st[v].ys), max_y) - st[v].ys.begin();
             ^~~
teams.cpp:16:8: note: shadowed declaration is here
 int n, kol, tt = 0;
        ^~~
teams.cpp:45:53: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         int kol = upper_bound(all(st[v].ys), max_y) - st[v].ys.begin();
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:54: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 can(int, int*)':
teams.cpp:140:21: warning: declaration of 'kol' shadows a global declaration [-Wshadow]
                 int kol = calc(1, 0, n - 1, events[it - 1].ft + 1, events[it].ft - 1);
                     ^~~
teams.cpp:16:8: note: shadowed declaration is here
 int n, kol, tt = 0;
        ^~~
teams.cpp:145:24: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         int kol_up = n - (upper_bound(all(lf), events[it].ft) - lf.begin());
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:146:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         int kol_lo = lower_bound(all(rt), events[it].ft) - rt.begin();
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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