oj.uz

Submission #971450

# Submission time Handle Problem Language Result Execution time Memory
971450 2024-04-28T14:14:10 Z andro Examination (JOI19_examination) C++14
20 / 100
 94 ms 18540 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){
        for(; i < N; i += i & - i) {
            t[i] += val;
        }
    }
    int query(int i) {
        int ans = 0;
        for(; i > 0; i -= i & - i) {
            ans += t[i];
        }
        return ans;
    }
    int query(int l, int r) {
        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;
        a[i].first += 1;
        a[i].second += 1;
    }
    if(n <= 3000 && q <= 3000) {
        for(int i = 1; i <= q; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            x += 1;
            y += 1;
            z += 1;
            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;
        x += 1;
        y += 1;
        z += 1;
        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:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>.
      |                         ^
examination.cpp: In function 'int main()':
examination.cpp:108:13: warning: unused variable 'ans' [-Wunused-variable]
  108 |         int ans = 0;
      |             ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 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 516 KB Output is correct
8 Correct 36 ms 348 KB Output is correct
9 Correct 37 ms 344 KB Output is correct
10 Correct 37 ms 348 KB Output is correct
11 Correct 37 ms 344 KB Output is correct
12 Incorrect 36 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 17028 KB Output is correct
2 Correct 75 ms 17240 KB Output is correct
3 Correct 89 ms 17488 KB Output is correct
4 Correct 71 ms 17232 KB Output is correct
5 Correct 52 ms 16496 KB Output is correct
6 Correct 49 ms 16284 KB Output is correct
7 Correct 68 ms 17144 KB Output is correct
8 Correct 77 ms 17228 KB Output is correct
9 Correct 65 ms 16980 KB Output is correct
10 Correct 47 ms 15308 KB Output is correct
11 Correct 73 ms 16980 KB Output is correct
12 Correct 41 ms 14640 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 17028 KB Output is correct
2 Correct 75 ms 17240 KB Output is correct
3 Correct 89 ms 17488 KB Output is correct
4 Correct 71 ms 17232 KB Output is correct
5 Correct 52 ms 16496 KB Output is correct
6 Correct 49 ms 16284 KB Output is correct
7 Correct 68 ms 17144 KB Output is correct
8 Correct 77 ms 17228 KB Output is correct
9 Correct 65 ms 16980 KB Output is correct
10 Correct 47 ms 15308 KB Output is correct
11 Correct 73 ms 16980 KB Output is correct
12 Correct 41 ms 14640 KB Output is correct
13 Incorrect 94 ms 18540 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 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 516 KB Output is correct
8 Correct 36 ms 348 KB Output is correct
9 Correct 37 ms 344 KB Output is correct
10 Correct 37 ms 348 KB Output is correct
11 Correct 37 ms 344 KB Output is correct
12 Incorrect 36 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -