Submission #31000

#	Time	Username	Problem	Language	Result	Execution time	Memory
31000		kajebiii	Teams (IOI15_teams)	C++14	100 / 100	3106 ms	367292 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 5e5 + 100, DEBUG = 0;

struct NODE{
    int cnt;
    NODE *lp, *rp;
    NODE(int c) : cnt(c), lp(NULL), rp(NULL) {}
    NODE(int a, int b) : cnt(0), lp(NULL), rp(NULL) {
        if(a == b) return;
        int m = (a+b) >> 1;
        lp = new NODE(a, m);
        rp = new NODE(m+1, b);
    }
    NODE *add(int l, int r, int v) {
        if(r < v || v < l) return this;
        NODE *res = new NODE(cnt);
        int m = (l+r) >> 1;
        if(l != r) {
            res->lp = lp->add(l, m, v);
            res->rp = rp->add(m+1, r, v);
        }
        res->cnt++;
        return res;
    }
    int getCnt(int l, int r, int a, int b) {
        if(r < a || b < l) return 0;
        if(a <= l && r <= b) return cnt;
        int m = (l+r) >> 1;
        return lp->getCnt(l, m, a, b) + rp->getCnt(m+1, r, a, b);
    }
};
NODE *root[MAX_N];

int N, *A, *B; vector<pi> Ps;

vector<int> CoX, CoY;
void init(int n, int a[], int b[]) {
    N = n; A = a; B = b;
    for(int i=0; i<N; i++) {
        CoX.push_back(B[i]);
        CoY.push_back(A[i]);
        Ps.push_back(pi(B[i], A[i]));
    }
    sort(ALL(CoX)); sort(ALL(CoY));
    sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
    for(int i=0; i<N; i++) Ps[i].one = i+1;
    sort(ALL(Ps), [&](pi a, pi b) {return a.two < b.two;});    
    for(int i=0; i<N; i++) Ps[i].two = i+1;

if(DEBUG) {
    printf("Y : "); for(int i=0; i<N; i++) printf("%d ", CoY[i]); puts("");
    printf("X : "); for(int i=0; i<N; i++) printf("%d ", CoX[i]); puts("");
    for(int i=0; i<N; i++) printf("[%d %d] ", Ps[i].one, Ps[i].two); puts("");
}

    root[0] = new NODE(1, N);
    for(int i=0; i<N; i++)
        root[i+1] = root[i] -> add(1, N, Ps[i].one);

}

int getUix(int k, vector<int> &v) {
    return (upper_bound(ALL(v), k) - v.begin() - 1) + 1;
}
int getLix(int k, vector<int> &v) {
    return (lower_bound(ALL(v), k) - v.begin()) + 1;
}
bool isBetween(int k, int x, int y) {
    return x <= k && k <= y;
}
int getCnt(int x0, int x1, int y0, int y1) {
//    int cnt = 0;for(int i=0; i<N; i++) if(isBetween(Ps[i].one, x0, x1) & isBetween(Ps[i].two, y0, y1)) cnt++;
//    printf("[%d %d %d %d] => %d\n", x0, x1, y0, y1, cnt);
//    return cnt;
    return root[y1] -> getCnt(1, N, x0, x1) - root[y0-1] -> getCnt(1, N, x0, x1);
}
int findX(NODE *mp, NODE *pp, int l, int r, int v) {
    if(l == r) return l;
    int m = (l+r) >> 1;
    int lcnt = pp->lp->cnt - mp->lp->cnt;
    if(lcnt >= v) return findX(mp->lp, pp->lp, l, m, v);
    return findX(mp->rp, pp->rp, m+1, r, v-lcnt);
}

int M, *K;
int can(int m, int k[]) {
    M = m; K = k;
    sort(K, K+M);

    stack<pi> S; S.push(pi(0, MAX_N));  // (y, x);
    for(int mi=0; mi<M; mi++) {
        int v = K[mi];

        int yi = getUix(v, CoY);
        int xi = getLix(v, CoX);

//        printf("yi : %d | xi : %d\n", yi, xi);

        while(true) {
            while(S.top().two < xi) S.pop();
            int py, px; tie(py, px) = S.top();
            int cnt = getCnt(xi, px, py+1, yi);
            if(cnt >= v) {
                int base = getCnt(1, xi-1, py+1, yi);
                int newX = findX(root[py], root[yi], 1, N, v+base);
                S.push(pi(yi, newX));
                break;
            }else{
                v -= cnt;
                xi = px+1;
                S.pop();
                if(S.size() == 0) {
                    return 0;
                }
            }
        }
    }
	return 1;
}

Compilation message (stderr)

teams.cpp: In lambda function:
teams.cpp:62:33: warning: declaration of 'pi b' shadows a parameter [-Wshadow]
     sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
                                 ^
teams.cpp:54:33: note: shadowed declaration is here
 void init(int n, int a[], int b[]) {
                                 ^
teams.cpp:62:33: warning: declaration of 'pi a' shadows a parameter [-Wshadow]
     sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
                                 ^
teams.cpp:54:24: note: shadowed declaration is here
 void init(int n, int a[], int b[]) {
                        ^
teams.cpp: In lambda function:
teams.cpp:64:33: warning: declaration of 'pi b' shadows a parameter [-Wshadow]
     sort(ALL(Ps), [&](pi a, pi b) {return a.two < b.two;});    
                                 ^
teams.cpp:54:33: note: shadowed declaration is here
 void init(int n, int a[], int b[]) {
                                 ^
teams.cpp:64:33: warning: declaration of 'pi a' shadows a parameter [-Wshadow]
     sort(ALL(Ps), [&](pi a, pi b) {return a.two < b.two;});    
                                 ^
teams.cpp:54:24: note: shadowed declaration is here
 void init(int n, int a[], int b[]) {
                        ^
teams.cpp: In function 'int getUix(int, std::vector<int>&)':
teams.cpp:80:55: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
     return (upper_bound(ALL(v), k) - v.begin() - 1) + 1;
                                                       ^
teams.cpp: In function 'int getLix(int, std::vector<int>&)':
teams.cpp:83:51: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
     return (lower_bound(ALL(v), k) - v.begin()) + 1;
                                                   ^

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