oj.uz

답안 #559824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559824 2022-05-10T17:13:24 Z emuyumi 팀들 (IOI15_teams) C++17
100 / 100
 3566 ms 175740 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Segtree{

#define mid ((l + r) >> 1)

    struct Node{
        int lc, rc, val;
    };

    int N;
    vector<Node> st;
    int T;

    Segtree() = default;
    Segtree(int N) : N(N) {
        st.resize(25 * N);
        T = 0;

        build(0, 1, N);
    }

    int build(int v, int l, int r){
        if (l == r) return v;
        st[v].lc = build(++T, l, mid);
        st[v].rc = build(++T, mid + 1, r);
        return v;
    }

    int insert(int v, int l, int r, int idx){
        int nv = ++T;
        if (l == r){
            st[nv] = {0, 0, st[v].val + 1};
        }
        else if (idx <= mid){
            st[nv].lc = insert(st[v].lc, l, mid, idx);
            st[nv].rc = st[v].rc;
            st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
        }
        else{
            st[nv].lc = st[v].lc;
            st[nv].rc = insert(st[v].rc, mid + 1, r, idx);
            st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
        }
        return nv;
    }
    int insert(int v, int idx){ return insert(v, 1, N, idx); }

    int query(int vl, int vr, int l, int r, int ql, int qr){
        if (l > qr || r < ql || ql > qr) return 0;
        if (l >= ql && r <= qr) return st[vr].val - st[vl].val;
        return query(st[vl].lc, st[vr].lc, l, mid, ql, qr) +
               query(st[vl].rc, st[vr].rc, mid + 1, r, ql, qr);
    }
    int query(int vl, int vr, int ql, int qr){ return query(vl, vr, 1, N, ql, qr); }

#undef mid
};

using pii = pair<int, int>;

Segtree st;
vector<int> rts;
int N;
vector<pii> xs, ys;

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

    for (int i = 0; i < N; ++i){
        xs.push_back({A[i], i});
        ys.push_back({B[i], i});
    }

    // give each point unique x and unique y
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());

    vector<int> y(N + 1);
    for (int i = 0; i < N; ++i){
        int x = lower_bound(xs.begin(), xs.end(), pii{A[i], i}) - xs.begin() + 1;
        y[x] = lower_bound(ys.begin(), ys.end(), pii{B[i], i}) - ys.begin() + 1;
// cerr << x << " " << y[x] << '\n';
    }

    st = Segtree(N + 1);
    rts.resize(N + 1);
    int v = 0;

    for (int x = 1; x <= N; ++x){
        v = st.insert(v, y[x]);
        rts[x] = v;
    }
}

// number of points in [x1, x2] x [y1, y2]
int count(int x1, int x2, int y1, int y2){
    x2 = min(x2, N);
    y2 = min(y2, N);
    return st.query(rts[x1 - 1], rts[x2], y1, y2);
}

int can(int M, int K[]){
    sort(K, K + M);
    struct Point{ int x, y; };

    vector<Point> stk = {};
    stk.push_back({0, N + 1});

    for (int i = 0; i < M; ++i){
        int qx = upper_bound(xs.begin(), xs.end(), pii{K[i], 1e9}) - xs.begin() + 1 - 1;
        int qy = lower_bound(ys.begin(), ys.end(), pii{K[i], -1}) - ys.begin() + 1;

        while (stk.back().y < qy){
            stk.pop_back();
        }

        int need = K[i];
        while (need){
            if (stk.empty()){
                return 0;
            }
            auto [lx, ly] = stk.back();

            /*
            
            **........^
            **........^
            *****%%%%%% ly
            *****%%%%%% qy
            ***********
            ***********
                lx    qx
            */
            int rect = count(lx + 1, qx, qy, ly);
// cerr << lx + 1 << " " << qx << " " << qy << " " << ly << '\n';
// cerr << rect << '\n';
            if (rect <= need){
                need -= rect;
                qy = ly + 1;
                stk.pop_back();
            }
            else{
                // bsearch for new y
                int lo = qy - 1, hi = ly;
                while (lo < hi){
                    int mi = (lo + hi) >> 1;
                    int cnt = count(lx + 1, qx, qy, mi);
                    if (cnt >= need) hi = mi;
                    else lo = mi + 1;
                }
                need = 0;
                qy = lo + 1;
            }
        }
        stk.push_back({qx, qy - 1});
    }
    return 1;
}

Compilation message

teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
   19 |     Segtree(int N) : N(N) {
      |             ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
   14 |     int N;
      |         ^
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
   19 |     Segtree(int N) : N(N) {
      |             ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
   14 |     int N;
      |         ^
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
   19 |     Segtree(int N) : N(N) {
      |             ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
   14 |     int N;
      |         ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:70:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   70 | void init(int N, int A[], int B[]){
      |           ~~~~^
teams.cpp:67:5: note: shadowed declaration is here
   67 | int N;
      |     ^
teams.cpp:84:78: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   84 |         int x = lower_bound(xs.begin(), xs.end(), pii{A[i], i}) - xs.begin() + 1;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:85:77: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   85 |         y[x] = lower_bound(ys.begin(), ys.end(), pii{B[i], i}) - ys.begin() + 1;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:114:85: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  114 |         int qx = upper_bound(xs.begin(), xs.end(), pii{K[i], 1e9}) - xs.begin() + 1 - 1;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:115:80: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  115 |         int qy = lower_bound(ys.begin(), ys.end(), pii{K[i], -1}) - ys.begin() + 1;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 300 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 33892 KB Output is correct
2 Correct 105 ms 33996 KB Output is correct
3 Correct 102 ms 33848 KB Output is correct
4 Correct 102 ms 34216 KB Output is correct
5 Correct 77 ms 33560 KB Output is correct
6 Correct 88 ms 33512 KB Output is correct
7 Correct 76 ms 33472 KB Output is correct
8 Correct 87 ms 33524 KB Output is correct
9 Correct 180 ms 33720 KB Output is correct
10 Correct 121 ms 33228 KB Output is correct
11 Correct 70 ms 33308 KB Output is correct
12 Correct 61 ms 33404 KB Output is correct
13 Correct 92 ms 33692 KB Output is correct
14 Correct 84 ms 33672 KB Output is correct
15 Correct 87 ms 33864 KB Output is correct
16 Correct 93 ms 33816 KB Output is correct
17 Correct 75 ms 33880 KB Output is correct
18 Correct 74 ms 33868 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 34392 KB Output is correct
2 Correct 103 ms 34232 KB Output is correct
3 Correct 635 ms 37608 KB Output is correct
4 Correct 97 ms 34016 KB Output is correct
5 Correct 134 ms 33872 KB Output is correct
6 Correct 130 ms 33840 KB Output is correct
7 Correct 83 ms 33868 KB Output is correct
8 Correct 129 ms 33928 KB Output is correct
9 Correct 166 ms 33640 KB Output is correct
10 Correct 509 ms 33484 KB Output is correct
11 Correct 616 ms 33664 KB Output is correct
12 Correct 741 ms 33876 KB Output is correct
13 Correct 1010 ms 34312 KB Output is correct
14 Correct 889 ms 36116 KB Output is correct
15 Correct 324 ms 34348 KB Output is correct
16 Correct 407 ms 34360 KB Output is correct
17 Correct 277 ms 34276 KB Output is correct
18 Correct 365 ms 34268 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 723 ms 170032 KB Output is correct
2 Correct 730 ms 170148 KB Output is correct
3 Correct 2462 ms 175740 KB Output is correct
4 Correct 722 ms 169648 KB Output is correct
5 Correct 616 ms 167340 KB Output is correct
6 Correct 618 ms 167400 KB Output is correct
7 Correct 455 ms 167408 KB Output is correct
8 Correct 555 ms 167444 KB Output is correct
9 Correct 1018 ms 167600 KB Output is correct
10 Correct 1490 ms 165668 KB Output is correct
11 Correct 2023 ms 166424 KB Output is correct
12 Correct 2598 ms 167340 KB Output is correct
13 Correct 3566 ms 168892 KB Output is correct
14 Correct 3068 ms 172520 KB Output is correct
15 Correct 1230 ms 170040 KB Output is correct
16 Correct 1236 ms 169908 KB Output is correct
17 Correct 1046 ms 169260 KB Output is correct
18 Correct 1053 ms 169396 KB Output is correct