oj.uz

답안 #971452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971452 2024-04-28T14:17:11 Z andro Examination (JOI19_examination) C++14
2 / 100
 75 ms 17052 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 4e5 + 5;

struct fenw {
    int t[N];
    void add(int i, int val){
        i += 1;
        for(; i < N; i += i & - i) {
            t[i] += val;
        }
    }
    int query(int i) {
        int ans = 0;
        i += 1;
        for(; i > 0; i -= i & - i) {
            ans += t[i];
        }
        return ans;
    }
    int query(int l, int r) {
        l += 1;
        r += 1;
        return query(r) - query(l - 1);
    }
}fenw1, fenw2;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<pair<int,int>> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    if(n <= 3000 && q <= 3000) {
        for(int i = 1; i <= q; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            int ans = 0;
            for(int j = 1; j <= n; j++) {
                if(a[j].first >= x && a[j].second >= y && a[j].first + a[j].second >= z) {
                    ans += 1;
                }
            }
            cout << ans << "\n";
        }
        return 0;
    }
    sort(a.begin() + 1, a.end());
    //cout << "\n";
    for(int i = 1; i <= n; i++) {
        //cout << a[i].first << " " << a[i].second << "\n";
    }
    //cout << "\n";
    vector<pair<int,int>> query1[n + 1];
    vector<pair<int,int>> saberi2[n + 1];
    vector<pair<int,int>> oduzmi2[n + 1];
    int index = 1;
    vector<int> ans(q + 1, 0);
    while(q--) {
        int x, y, z;
        cin >> x >> y >> z;
        int l = 1, r = n, p = - 1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[mid].first >= x) {
                r = mid - 1;
                p = mid;
            }
            else {
                l = mid + 1;
            }
        }
        if(p == - 1) {
            index += 1;
            continue;
        }
        /*
        int ans = 0;
        for(int i = p; i <= n; i++) {
            if(a[i].second >= max(z - a[i].first, y)) {
                ans += 1;
            }
        }
        cout << ans << "\n";*/
        //query[p].push_back({{y, z}, index++});
        l = p, r = n; int g = - 1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(z - a[mid].first >= y) {
                l = mid + 1;
                g = mid;
            }
            else {
                r = mid - 1;
            }
        }
        int ans = 0;
        //cout << index << " " << p << " " << g << "\n";
        if(g == - 1) {
            /*
            for(int i = p; i <= n; i++) {
                if(a[i].second >= y) {
                    ans += 1;
                }
            }*/
            query1[p].push_back({y, index++});
        }
        else {
            /*
            for(int i = p; i <= g; i++) {
                if(a[i].first + a[i].second >= z) {
                    ans += 1;
                }
            }*/
            saberi2[p].push_back({z, index});
            if(g + 1 <= n )
                oduzmi2[g + 1].push_back({z, index});
            /*
            for(int i = g + 1; i <= n; i++) {
                if(a[i].second >= y) {
                    ans += 1;
                }
            }*/
            if(g + 1 <= n) {
                query1[g + 1].push_back({y, index++});
            }
            else {
                index += 1;
            }
        }
    }
    for(int i = n; i > 0; i--) {
        fenw1.add(a[i].second, 1);
        fenw2.add(a[i].first + a[i].second, 1);
        for(auto it : query1[i]) {
            ans[it.second] += fenw1.query(it.first, N - 1);
            /*
            for(int j = i; j <= n; j += 1) {
                if(a[j].second >= it.first) {
                    ans[it.second] += 1;
                }
            }*/
        }
        for(auto it : saberi2[i]) {
            ans[it.second] += fenw2.query(it.first, N - 1);
            /*
            for(int j = i; j <= n; j += 1) {
                if(a[j].first + a[j].second >= it.first) {
                    ans[it.second] += 1;
                }
            }*/
        }
        for(auto it : oduzmi2[i]) {
            ans[it.second] -= fenw2.query(it.first, N - 1);
            /*
            for(int j = i; j <= n; j += 1) {
                if(a[j].first + a[j].second >= it.first) {
                    ans[it.second] -= 1;
                }
            }*/
        }
    }
    for(int i = 1; i < index; i++) {
        cout << ans[i] << "\n";
    }
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:104:13: warning: unused variable 'ans' [-Wunused-variable]
  104 |         int ans = 0;
      |             ^~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 37 ms 760 KB Output is correct
8 Correct 36 ms 600 KB Output is correct
9 Correct 37 ms 516 KB Output is correct
10 Correct 37 ms 348 KB Output is correct
11 Correct 38 ms 344 KB Output is correct
12 Correct 38 ms 524 KB Output is correct
13 Correct 38 ms 344 KB Output is correct
14 Correct 37 ms 344 KB Output is correct
15 Correct 37 ms 348 KB Output is correct
16 Correct 17 ms 344 KB Output is correct
17 Correct 26 ms 512 KB Output is correct
18 Correct 9 ms 604 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 17052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 17052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 37 ms 760 KB Output is correct
8 Correct 36 ms 600 KB Output is correct
9 Correct 37 ms 516 KB Output is correct
10 Correct 37 ms 348 KB Output is correct
11 Correct 38 ms 344 KB Output is correct
12 Correct 38 ms 524 KB Output is correct
13 Correct 38 ms 344 KB Output is correct
14 Correct 37 ms 344 KB Output is correct
15 Correct 37 ms 348 KB Output is correct
16 Correct 17 ms 344 KB Output is correct
17 Correct 26 ms 512 KB Output is correct
18 Correct 9 ms 604 KB Output is correct
19 Incorrect 75 ms 17052 KB Output isn't correct
20 Halted 0 ms 0 KB -