Submission #863971

# Submission time Handle Problem Language Result Execution time Memory
863971 2023-10-21T15:15:59 Z prohacker Examination (JOI19_examination) C++14
0 / 100
3000 ms 364780 KB
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int N = 1e5+10;
const int INF = 1e9;
const int mod = 1e9+7;

int n,t,ans[N];
map<pair<int,int>,int> bit;
pair<int,int> a[N];
struct Node{
    int l,r,all,id;
}q[N];

void update(int x, int y, int val) {
    while(x > 0) {
        int _y = y;
        while(_y > 0) {
            bit[{x,_y}] += val;
            _y -= (_y & (-_y));
        }
        x -= (x & (-x));
    }
}

int get(int x, int y) {
    int res = 0;
    while(x <= N) {
        int _y = y;
        while(_y <= N) {
            res += bit[{x,_y}];
            _y += (_y & (-_y));
        }
        x += (x & (-x));
    }
    return res;
}

signed main()
{
    if (fopen("Examination.inp", "r")) {
        freopen("Examination.inp", "r", stdin);
        freopen("Examination.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> t;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i].first >> a[i].second;
        a[i].first++;
        a[i].second++;
    }
    for(int i = 1 ; i <= t ; i++) {
        cin >> q[i].l >> q[i].r >> q[i].all;
        q[i].l++;
        q[i].r++;
        q[i].id = i;
        q[i].all += 2;
    }
    sort(q+1,q+t+1,[](Node u, Node v) {
        return u.all > v.all;
    });
    sort(a+1,a+n+1,[](pair<int,int> u, pair<int,int> v) {
        return u.first+u.second > v.first+v.second;
    });
    for(int i = 1,j = 1 ; i <= t ; i++) {
        while(j > 0 && a[j].first+a[j].second >= q[i].all) {
            update(a[j].first,a[j].second,1);
            j++;
        }
        ans[q[i].id] = get(q[i].l,q[i].r);
    }
    for(int i = 1 ; i <= t ; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("Examination.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen("Examination.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 364780 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 364780 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -