Submission #863970

#	Time	Username	Problem	Language	Result	Execution time	Memory
863970		prohacker	Examination (JOI19_examination)	C++14	2 / 100	3057 ms	352416 KiB

examination

#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 <= INF) {
        int _y = y;
        while(_y <= INF) {
            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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57