oj.uz

답안 #715223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715223 2023-03-26T08:36:29 Z TheSahib Examination (JOI19_examination) C++17
0 / 100
 3000 ms 1005308 KB 
#include <bits/stdc++.h>


#define ll long long
#define pii pair<int, int>

using namespace std;

const int TREE_SIZE = 1e5 * 40;
const int MAXVAL = (1 << 30) - 1;

struct SegTree1D{
    vector<int> tree, L, R;
    int nxt = 0;
    SegTree1D(){
        addNode();
    }
    int addNode(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
        return nxt++;
    }
    void update(int node, int l, int r, int pos, int val){
        tree[node] += val;
        if(l == r) return;
        int mid = (l + r) / 2;
        if(pos <= mid){
            if(!L[node]) L[node] = addNode();
            update(L[node], l, mid, pos, val);
        }
        else{
            if(!R[node]) R[node] = addNode();
            update(R[node], mid + 1, r, pos, val);
        }
    }

    int ask(int node, int l, int r, int ql, int qr){
        if(r < ql || qr < l) return 0;
        if(ql <= l && r <= qr) return tree[node];
        
        int ans = 0;
        int mid = (l + r) / 2;
        if(L[node]) ans += ask(L[node], l, mid, ql, qr);
        if(R[node]) ans += ask(R[node], mid + 1, r, ql, qr);
        return ans;
    }
};

struct SegTree2D{
    SegTree1D tree[TREE_SIZE];
    int L[TREE_SIZE], R[TREE_SIZE];
    int nxt = 0;

    int addNode(){
        return nxt++;
    }

    SegTree2D(){
        addNode();
        memset(L, 0, sizeof(L));
        memset(R, 0, sizeof(R));
    }
    void update(int node, int l, int r, int ux, int uy, int val){
        tree[node].update(0, 0, MAXVAL, ux, val);
        if(l == r) return;
        int mid = (l + r) / 2;
        if(uy <= mid){
            if(!L[node]) L[node] = addNode();
            update(L[node], l, mid, ux, uy, val);
        }
        else{
            if(!R[node]) R[node] = addNode();
            update(R[node], mid + 1, r, ux, uy, val);
        }
    }
    int ask(int node, int l, int r, int x1, int x2, int y1, int y2){
        if(r < y1 || y2 < l) return 0;
        if(y1 <= l && r <= y2) return tree[node].ask(0, 0, MAXVAL, x1, x2);
        
        int ans = 0;
        int mid = (l + r) / 2;
        if(L[node]) ans += ask(L[node], l, mid, x1, x2, y1, y2);
        if(R[node]) ans += ask(R[node], mid + 1, r, x1, x2, y1, y2);
        return ans;
    }
};


bool comp1(pii p1, pii p2){
    return (p1.first + p1.second) < (p2.first + p2.second);
}

bool comp2(array<int, 4>& a1, array<int, 4>& a2){
    return a1[2] < a2[2];
}

int main(){
    SegTree2D tree;
    int n, q; cin >> n >> q;
    vector<pii> scores(n);
    for (int i = 0; i < n; i++)
    {
        cin >> scores[i].first >> scores[i].second;
        tree.update(0, 0, MAXVAL, scores[i].first, scores[i].second, 1);
    }
    sort(scores.begin(), scores.end(), comp1);
    vector<array<int, 4>> querries(q);
    for (int i = 0; i < q; i++)
    {
        cin >> querries[i][0] >> querries[i][1] >> querries[i][2];
        querries[i][3] = i;
    }
    sort(querries.begin(), querries.end(), comp2);

    int ans[q];
    int last = 0;
    for (int i = 0; i < q; i++)
    {
        int l = 0, r = n - 1;
        int low = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            if(scores[mid].first + scores[mid].second < querries[i][2]){
                l = mid + 1;
                low = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        while(last < low){
            tree.update(0, 0, MAXVAL, scores[last].first, scores[last].second, -1);
            last++;
        }
        ans[querries[i][3]] = n - last;
        if(querries[i][0] != 0){
            ans[querries[i][3]] -= tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, MAXVAL);
        }
        if(querries[i][1] != 0){
            ans[querries[i][3]] -= tree.ask(0, 0, MAXVAL, 0, MAXVAL, 0, querries[i][1] - 1);
        }
        if(querries[i][1] != 0 && querries[i][2] != 0){
            ans[querries[i][3]] += tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, querries[i][1] - 1);
        }
    }
    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << '\n';
    }
    
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 595 ms 720420 KB Output is correct
2 Correct 642 ms 720380 KB Output is correct
3 Correct 632 ms 720484 KB Output is correct
4 Correct 737 ms 720484 KB Output is correct
5 Correct 615 ms 720584 KB Output is correct
6 Correct 624 ms 720452 KB Output is correct
7 Correct 905 ms 753524 KB Output is correct
8 Correct 920 ms 753740 KB Output is correct
9 Correct 979 ms 753504 KB Output is correct
10 Correct 951 ms 744060 KB Output is correct
11 Correct 912 ms 741100 KB Output is correct
12 Incorrect 693 ms 720432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3095 ms 1005308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3095 ms 1005308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 595 ms 720420 KB Output is correct
2 Correct 642 ms 720380 KB Output is correct
3 Correct 632 ms 720484 KB Output is correct
4 Correct 737 ms 720484 KB Output is correct
5 Correct 615 ms 720584 KB Output is correct
6 Correct 624 ms 720452 KB Output is correct
7 Correct 905 ms 753524 KB Output is correct
8 Correct 920 ms 753740 KB Output is correct
9 Correct 979 ms 753504 KB Output is correct
10 Correct 951 ms 744060 KB Output is correct
11 Correct 912 ms 741100 KB Output is correct
12 Incorrect 693 ms 720432 KB Output isn't correct
13 Halted 0 ms 0 KB -