oj.uz

Submission #30998

# Submission time Handle Problem Language Result Execution time Memory
30998 2017-08-03T08:09:39 Z kajebiii Teams (IOI15_teams) C++14
77 / 100
 4000 ms 365972 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 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 = -1;
                for(int l=xi, r=px; l<=r; ) {
                    int m = (l+r) >> 1;
                    int now = getCnt(xi, m, py+1, yi);
                    if(now == v) {newX = m; break;}
                    if(now < v) l = m+1; else r = m-1;
                }
                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;
                                                   ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:116:25: warning: declaration of 'int m' shadows a parameter [-Wshadow]
                     int m = (l+r) >> 1;
                         ^
teams.cpp:96:13: note: shadowed declaration is here
 int can(int m, int k[]) {
             ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5960 KB Output is correct
2 Correct 0 ms 5960 KB Output is correct
3 Correct 0 ms 5960 KB Output is correct
4 Correct 0 ms 5960 KB Output is correct
5 Correct 0 ms 5960 KB Output is correct
6 Correct 0 ms 6108 KB Output is correct
7 Correct 0 ms 5960 KB Output is correct
8 Correct 0 ms 5960 KB Output is correct
9 Correct 0 ms 5960 KB Output is correct
10 Correct 0 ms 5960 KB Output is correct
11 Correct 0 ms 5960 KB Output is correct
12 Correct 6 ms 5960 KB Output is correct
13 Correct 3 ms 5960 KB Output is correct
14 Correct 0 ms 5960 KB Output is correct
15 Correct 0 ms 5960 KB Output is correct
16 Correct 0 ms 5960 KB Output is correct
17 Correct 0 ms 5960 KB Output is correct
18 Correct 0 ms 5960 KB Output is correct
19 Correct 0 ms 5960 KB Output is correct
20 Correct 0 ms 5960 KB Output is correct
21 Correct 0 ms 5960 KB Output is correct
22 Correct 0 ms 5960 KB Output is correct
23 Correct 0 ms 5960 KB Output is correct
24 Correct 0 ms 5960 KB Output is correct
25 Correct 0 ms 5960 KB Output is correct
26 Correct 0 ms 5960 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 70392 KB Output is correct
2 Correct 166 ms 70392 KB Output is correct
3 Correct 143 ms 70392 KB Output is correct
4 Correct 163 ms 70800 KB Output is correct
5 Correct 123 ms 70392 KB Output is correct
6 Correct 126 ms 70392 KB Output is correct
7 Correct 96 ms 70392 KB Output is correct
8 Correct 96 ms 70392 KB Output is correct
9 Correct 389 ms 70536 KB Output is correct
10 Correct 266 ms 70392 KB Output is correct
11 Correct 113 ms 70392 KB Output is correct
12 Correct 116 ms 70392 KB Output is correct
13 Correct 163 ms 70392 KB Output is correct
14 Correct 159 ms 70392 KB Output is correct
15 Correct 206 ms 70392 KB Output is correct
16 Correct 153 ms 70392 KB Output is correct
17 Correct 123 ms 70392 KB Output is correct
18 Correct 133 ms 70392 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 70788 KB Output is correct
2 Correct 213 ms 70788 KB Output is correct
3 Correct 1676 ms 73428 KB Output is correct
4 Correct 196 ms 70800 KB Output is correct
5 Correct 369 ms 70788 KB Output is correct
6 Correct 423 ms 70788 KB Output is correct
7 Correct 129 ms 70788 KB Output is correct
8 Correct 379 ms 70788 KB Output is correct
9 Correct 383 ms 70536 KB Output is correct
10 Correct 1096 ms 70696 KB Output is correct
11 Correct 1423 ms 70792 KB Output is correct
12 Correct 2013 ms 70788 KB Output is correct
13 Correct 2583 ms 70788 KB Output is correct
14 Correct 2193 ms 72108 KB Output is correct
15 Correct 703 ms 70788 KB Output is correct
16 Correct 729 ms 70788 KB Output is correct
17 Correct 626 ms 70788 KB Output is correct
18 Correct 943 ms 70788 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 361880 KB Output is correct
2 Correct 1309 ms 361880 KB Output is correct
3 Execution timed out 4000 ms 365972 KB Execution timed out
4 Halted 0 ms 0 KB -