oj.uz

Submission #971451

# Submission time Handle Problem Language Result Execution time Memory
971451 2024-04-28T14:15:26 Z andro Examination (JOI19_examination) C++14
2 / 100
 3000 ms 16456 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;
    }
    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:100:13: warning: unused variable 'ans' [-Wunused-variable]
  100 |         int ans = 0;
      |             ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 37 ms 520 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 344 KB Output is correct
11 Correct 38 ms 348 KB Output is correct
12 Correct 38 ms 348 KB Output is correct
13 Correct 37 ms 604 KB Output is correct
14 Correct 37 ms 644 KB Output is correct
15 Correct 37 ms 632 KB Output is correct
16 Correct 17 ms 604 KB Output is correct
17 Correct 26 ms 604 KB Output is correct
18 Correct 7 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 16456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 16456 KB Time limit exceeded
2 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 37 ms 520 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 344 KB Output is correct
11 Correct 38 ms 348 KB Output is correct
12 Correct 38 ms 348 KB Output is correct
13 Correct 37 ms 604 KB Output is correct
14 Correct 37 ms 644 KB Output is correct
15 Correct 37 ms 632 KB Output is correct
16 Correct 17 ms 604 KB Output is correct
17 Correct 26 ms 604 KB Output is correct
18 Correct 7 ms 348 KB Output is correct
19 Execution timed out 3074 ms 16456 KB Time limit exceeded
20 Halted 0 ms 0 KB -