Submission #220745

#	Time	Username	Problem	Language	Result	Execution time	Memory
220745		VEGAnn	팀들 (IOI15_teams)	C++14	0 / 100	575 ms	524292 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;
const int oo = 2e9;
const int N = 500100;
vector<pii> vc;
int n, kol, tt = 0;

struct seg_tree{
    vector<int> ys, psh;
    vector<pii> st;

    seg_tree(): ys(0), st(0), psh(0) {}

    void pull(int v){
        st[v].ft = max(st[v + v].ft, st[v + v + 1].ft);
        st[v].sd = 0;

        if (st[v].ft == st[v + v].ft)
            st[v].sd += st[v + v].sd;

        if (st[v].ft == st[v + v + 1].ft)
            st[v].sd += st[v + v + 1].sd;
    }

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

        if (l == r){
            st[v] = MP(0, 1);
            return;
        }

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

        pull(v);
    }

    void push(int v, int l, int r){
        if (psh[v] != 0){
            if (psh[v] >= st[v].ft){
                st[v] = MP(psh[v], r - l + 1);
            }

            if (l != r){
                psh[v + v] = max(psh[v + v], psh[v]);
                psh[v + v + 1] = max(psh[v + v + 1], psh[v]);
            }

            psh[v] = 0;
        }
    }

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

        if (l > r) return;

        if (tl == l && tr == r){
            psh[v] = vl;
            push(v, tl, tr);
            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);

        pull(v);
    }

    pii get(int v, int tl, int tr, int l, int r){
        push(v, tl, tr);

        if (l > r) return MP(0, 0);

        if (tl == l && tr == r) return st[v];

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

        pii n1 = get(v + v, tl, md, l, min(r, md));
        pii n2 = get(v + v + 1, md + 1, tr, max(md + 1, l), r);

        pii res = MP(max(n1.ft, n2.ft), 0);

        if (res.ft == n1.ft) res.sd += n1.sd;
        if (res.ft == n2.ft) res.sd += n2.sd;

        return res;
    }
};

seg_tree st[4 * N];
pii psh[4 * N];

void build(int v, int l, int r){
    psh[v] = MP(0, 0);

    if (l == r){
        st[v].ys.clear();
        st[v].ys.PB(vc[l].sd);

        st[v].st.resize(2);
        st[v].psh.resize(2);

        st[v].st[1] = MP(0, 1);
        st[v].psh[1] = 0;

        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));
    st[v].st.resize(sz(st[v].ys) * 4 + 3);
    st[v].psh.resize(sz(st[v].ys) * 4 + 3);
    st[v].build(1, 0, sz(st[v].ys) - 1);
}

void push(int v){
    if (psh[v] != MP(0, 0)){
        int loc = upper_bound(all(st[v].ys), psh[v].sd) - st[v].ys.begin() - 1;

        st[v].update(1, 0, sz(st[v].ys) - 1, 0, loc, psh[v].ft);

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

        psh[v] = MP(0, 0);
    }
}

void real_search(int v, int l, int r, int vl){
    // may be here should be push

    if (l == r){
        kol = 0;
        psh[v] = MP(tt, vl);
        return;
    }

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

    push(v + v);
    push(v + v + 1);

    int loc = upper_bound(all(st[v + v].ys), vl) - st[v + v].ys.begin() - 1;
    int cur_kol = loc + 1;

    pii gt = st[v + v].get(1, 0, sz(st[v + v].ys) - 1, 0, loc);

    if (gt.ft == tt)
        cur_kol -= gt.sd;

    // if (cur_kol == kol) it may further optimize

    if (cur_kol >= kol)
        real_search(v + v, l, md, vl);
    else {
        psh[v + v] = MP(tt, vl);
        kol -= cur_kol;
        real_search(v + v + 1, md + 1, r, vl);
    }
}

void search(int v, int l, int r, int vl){
    push(v);

    if (kol == 0) return;
    if (vc[r].ft < vl) return;

    if (vc[l].ft >= vl){
        int loc = upper_bound(all(st[v].ys), vl) - st[v].ys.begin() - 1;
        int cur_kol = loc + 1;

        pii gt = st[v].get(1, 0, sz(st[v].ys) - 1, 0, loc);

        if (gt.ft == tt)
            cur_kol -= gt.sd;

        if (cur_kol <= kol){
            kol -= cur_kol;
            psh[v] = MP(tt, vl);
        } else real_search(v, l, r, vl);

        return;
    }

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

    search(v + v, l, md, vl);
    search(v + v + 1, md + 1, r, vl);
}

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

    vc.clear();

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

    sort(all(vc));

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

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

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

    for (int i = 0; i < M; i++){
        int k = K[i];

        kol = k;

        search(1, 0, n - 1, k);

        if (kol > 0)
            return 0;
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'seg_tree::seg_tree()':
teams.cpp:18:17: warning: 'seg_tree::st' will be initialized after [-Wreorder]
     vector<pii> st;
                 ^~
teams.cpp:17:21: warning:   'std::vector<int> seg_tree::psh' [-Wreorder]
     vector<int> ys, psh;
                     ^~~
teams.cpp:20:5: warning:   when initialized here [-Wreorder]
     seg_tree(): ys(0), st(0), psh(0) {}
     ^~~~~~~~
teams.cpp: In function 'void push(int)':
teams.cpp:133:76: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         int loc = upper_bound(all(st[v].ys), psh[v].sd) - st[v].ys.begin() - 1;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'void real_search(int, int, int, int)':
teams.cpp:160:73: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
     int loc = upper_bound(all(st[v + v].ys), vl) - st[v + v].ys.begin() - 1;
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'void search(int, int, int, int)':
teams.cpp:186:69: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
         int loc = upper_bound(all(st[v].ys), vl) - st[v].ys.begin() - 1;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:208:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:12:11: note: shadowed declaration is here
 const int N = 500100;
           ^

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