oj.uz

Submission #30999

# Submission time Handle Problem Language Result Execution time Memory
30999 2017-08-03T08:13:15 Z kajebiii Teams (IOI15_teams) C++14
0 / 100
 2423 ms 367292 KB 
#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 newX = findX(root[py], root[yi], 1, N, v);
                S.push(pi(yi, newX));
                break;
            }else{
                v -= cnt;
                xi = px+1;
                S.pop();
                if(S.size() == 0) {
                    return 0;
                }
            }
        }
    }
	return 1;
}

Compilation message

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
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5960 KB Output is correct
2 Incorrect 0 ms 5960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 70392 KB Output is correct
2 Correct 159 ms 70392 KB Output is correct
3 Correct 176 ms 70392 KB Output is correct
4 Correct 219 ms 70800 KB Output is correct
5 Correct 123 ms 70392 KB Output is correct
6 Correct 86 ms 70392 KB Output is correct
7 Correct 113 ms 70392 KB Output is correct
8 Correct 126 ms 70392 KB Output is correct
9 Correct 129 ms 70536 KB Output is correct
10 Correct 126 ms 70392 KB Output is correct
11 Correct 86 ms 70392 KB Output is correct
12 Correct 116 ms 70392 KB Output is correct
13 Incorrect 173 ms 70392 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 70788 KB Output is correct
2 Correct 186 ms 70788 KB Output is correct
3 Correct 696 ms 73428 KB Output is correct
4 Correct 213 ms 70800 KB Output is correct
5 Correct 243 ms 70788 KB Output is correct
6 Correct 186 ms 70788 KB Output is correct
7 Correct 99 ms 70788 KB Output is correct
8 Correct 156 ms 70788 KB Output is correct
9 Correct 113 ms 70536 KB Output is correct
10 Correct 173 ms 70696 KB Output is correct
11 Correct 166 ms 70792 KB Output is correct
12 Incorrect 256 ms 70788 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 361880 KB Output is correct
2 Correct 929 ms 361880 KB Output is correct
3 Correct 2423 ms 367292 KB Output is correct
4 Incorrect 1276 ms 361924 KB Output isn't correct
5 Halted 0 ms 0 KB -