Submission #1038908

# Submission time Handle Problem Language Result Execution time Memory
1038908 2024-07-30T08:54:48 Z 정민찬(#10987) Card Collection (JOI24_collection) C++17
0 / 100
0 ms 2396 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const int inf = 1e9 + 10;

struct SegmentTree{
    vector<int> tree;
    void init(int n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, -inf);
    }
    void update(int node, int s, int e, int tar, int val) {
        if (s > tar || tar > e) return;
        if (s == e) {
            tree[node] = val;
            return;
        }
        int mid = s + e >> 1;
        update(node*2, s, mid, tar, val);
        update(node*2+1, mid+1, e, tar, val);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    int Findleft(int node, int s, int e, int l, int r, int k) {
        if (l > e || s > r || tree[node] < k) return -1;
        if (s == e) return tree[node] >= k ? s : -1;
        int mid = s + e >> 1;
        int t = Findleft(node*2, s, mid, l, r, k);
        if (t != -1) return t;
        return Findleft(node*2+1, mid+1, e, l, r, k);
    }
    int Findright(int node, int s, int e, int l, int r, int k) {
        if (l > e || s > r || tree[node] < k) return -1;
        if (s == e) return tree[node] >= k ? s : -1;
        int mid = s + e >> 1;
        int t = Findright(node*2+1, mid+1, e, l, r, k);
        if (t != -1) return t;
        return Findright(node*2, s, mid, l, r, k);
    }
};

int N, M;
int A[200010], B[200010];
int QA[200010], QB[200010];

SegmentTree seg1, rseg2;
SegmentTree segA, segB;
SegmentTree rsegA, rsegB;

vector<int> solve() {
    vector<int> sA[N+M+1], sB[N+M+1], sQ[N+M+1];
    for (int i=1; i<=N; i++) {
        sA[A[i]].push_back(i);
        sB[B[i]].push_back(i);
        sQ[QB[i]].push_back(i);
    }
    vector<int> id(M);
    iota(id.begin(), id.end(), 1);
    sort(id.begin(), id.end(), [&] (int &u, int &v) {
        return QB[u] < QB[v];
    });
    vector<int> ret(M+1, 0);
    vector<int> prmxa(N+2, 0), prmxb(N+2, 0), prmna(N+2, 1e9), prmnb(N+2, 1e9);
    vector<int> sumxa(N+2, 0), sumxb(N+2, 0), sumna(N+2, 1e9), sumnb(N+2, 1e9);
    for (int i=1; i<=N; i++) {
        prmxa[i] = max(prmxa[i-1], A[i]);
        prmxb[i] = max(prmxb[i-1], B[i]);
        prmna[i] = min(prmna[i-1], A[i]);
        prmnb[i] = min(prmnb[i-1], B[i]);
    }
    for (int i=N; i>=1; i--) {
        sumxa[i] = max(sumxa[i+1], A[i]);
        sumxb[i] = max(sumxb[i+1], B[i]);
        sumna[i] = min(sumna[i+1], A[i]);
        sumnb[i] = min(sumnb[i+1], B[i]);
    }
    seg1.init(N); rseg2.init(N);
    segA.init(N); segB.init(N);
    rsegA.init(N); rsegB.init(N);
    for (int i=1; i<=N; i++) {
        segA.update(1, 1, N, i, A[i]);
        segB.update(1, 1, N, i, B[i]);
        rsegA.update(1, 1, N, i, -A[i]);
        rsegB.update(1, 1, N, i, -B[i]);
        rseg2.update(1, 1, N, i, -A[i]);
    }
    int p = 0;
    for (int Bx=1; Bx<=N+M; Bx ++) {
        for (auto &i : sB[Bx]) {
            seg1.update(1, 1, N, i, A[i]);
        }
        for (auto &i : sQ[Bx]) {
            if (sA[QA[i]].empty() || sB[QB[i]].empty()) continue;
            int lm = sB[QB[i]][0], rm = sA[QA[i]].back();
            if (lm > rm) continue;
            if (lm == rm) {
                if (lm != 1 && (prmxa[lm-1] < QA[i] || prmxb[lm-1] < QB[i]) && (prmna[lm-1] > QA[i] || prmnb[lm-1] > QB[i])) continue;
                if (rm != N && (sumxa[rm+1] < QA[i] || sumxb[rm+1] < QB[i]) && (sumna[rm+1] > QA[i] || sumnb[rm+1] > QB[i])) continue;
                ret[i] = 1;
                continue;
            }
            //cout << i << ' ' << lm << ' ' << rm << '\n';
            int lh = N+1;
            if (A[1] <= QA[i] && B[1] >= QB[i]) {
                lh = 1;
            }
            else {
                int nonA = rsegA.Findleft(1, 1, N, 1, N, -QA[i]);
                int nonB = segB.Findleft(1, 1, N, 1, N, QB[i]);
                int non;
                if (nonA == -1) non = nonB;
                else if (nonB == -1) non = nonA;
                else non = min(nonA, nonB);
                lh = rseg2.Findleft(1, 1, N, non+1, N, -QA[i]);
            }
            if (lh == -1 || lh > sB[QB[i]].back()) lh = N+1;
            else {
                int idx = lower_bound(sB[QB[i]].begin(), sB[QB[i]].end(), lh) - sB[QB[i]].begin();
                lh = sB[QB[i]][idx];
            }
            int rh = 0;
            if (A[N] >= QA[i] && B[N] <= QB[i]) {
                rh = N;
            }
            else {
                int nonA = segA.Findright(1, 1, N, 1, N, QA[i]);
                int nonB = rsegB.Findright(1, 1, N, 1, N, -QB[i]);
                int non;
                if (nonA == -1) non = nonB;
                else if (nonB == -1) non = nonA;
                else non = max(nonA, nonB);
                rh = seg1.Findright(1, 1, N, 1, non-1, QA[i]);
            }
            if (rh == -1 || rh < sA[QA[i]][0]) rh = 0;
            else {
                int idx = upper_bound(sA[QA[i]].begin(), sA[QA[i]].end(), rh) - sA[QA[i]].begin() - 1;
                rh = sA[QA[i]][idx];
            }
            int le = rseg2.Findleft(1, 1, N, lm+1, N, -QA[i]);
            if (le == -1) le = N+1;
            int re = seg1.Findright(1, 1, N, 1, rm-1, QA[i]);
            if (re == -1) re = 0;
            if (min(max(lh, lm), le) < max(min(rh, rm), re)) {
                ret[i] = 1;
            }
        }
        for (auto &i : sB[Bx]) {
            rseg2.update(1, 1, N, i, -inf);
        }
    }
    return ret;
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    vector<int> ta, tb;
    for (int i=1; i<=N; i++) {
        cin >> A[i] >> B[i];
        ta.push_back(A[i]);
        tb.push_back(B[i]);
    }

    for (int i=1; i<=M; i++) {
        cin >> QA[i] >> QB[i];
        ta.push_back(QA[i]);
        tb.push_back(QB[i]);
    }
    sort(ta.begin(), ta.end());
    ta.erase(unique(ta.begin(), ta.end()), ta.end());
    sort(tb.begin(), tb.end());
    tb.erase(unique(tb.begin(), tb.end()), tb.end());
    for (int i=1; i<=N; i++) {
        A[i] = lower_bound(ta.begin(), ta.end(), A[i]) - ta.begin() + 1;
        B[i] = lower_bound(tb.begin(), tb.end(), B[i]) - tb.begin() + 1;
    }
    for (int i=1; i<=M; i++) {
        QA[i] = lower_bound(ta.begin(), ta.end(), QA[i]) - ta.begin() + 1;
        QB[i] = lower_bound(tb.begin(), tb.end(), QB[i]) - tb.begin() + 1;
    }
    vector<int> ret[4];
    ret[0] = solve();
    reverse(A+1, A+N+1);
    reverse(B+1, B+N+1);
    ret[1] = solve();
    for (int i=1; i<=N; i++) {
        A[i] = ta.size() - A[i] + 1;
        B[i] = tb.size() - B[i] + 1;
    }
    for (int i=1; i<=M; i++) {
        QA[i] = ta.size() - QA[i] + 1;
        QB[i] = tb.size() - QB[i] + 1;
    }
    ret[2] = solve();
    reverse(A+1, A+N+1);
    reverse(B+1, B+N+1);
    ret[3] = solve();
    for (int i=1; i<=M; i++) {
        int flag = 0;
        for (int j=0; j<4; j++) {
            flag |= ret[j][i];
        }
        if (flag) cout << i << ' ';
    }
}

Compilation message

Main.cpp: In member function 'void SegmentTree::init(int)':
Main.cpp:13:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   13 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
Main.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int SegmentTree::Findleft(int, int, int, int, int, int)':
Main.cpp:30:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int SegmentTree::Findright(int, int, int, int, int, int)':
Main.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In function 'std::vector<int> solve()':
Main.cpp:90:9: warning: unused variable 'p' [-Wunused-variable]
   90 |     int p = 0;
      |         ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -