Submission #1279186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279186		swishy123	Examination (JOI19_examination)	C++20	0 / 100	697 ms	68548 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pi pair<int, int>
#define x first
#define y second

const int inf = 1e9;
const int def = 1e5+1;
using namespace std;
using namespace __gnu_pbds;

template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Query{
    int x, y, z, indx;
};

ordset<pi> bit[100100];
void insert(int x, int y){
	for(int i = x; i < def; i += i & -i)
		bit[i].insert({y, x});
}
 
int query(int x, int y){
	if (x == 0 || y == 0) return 0;
	int ans = 0;
	for (int i = x; i > 0; i -= i & -i)
		ans += bit[i].order_of_key({y + 1, 0});
 
	return ans;
}
 
void solve(){
    int n, q;
    cin >> n >> q;

    vector<pair<int, int>> v;
    vector<int> vs;

    for (int i = 0; i < n; i++){
        int s, t;
        cin >> s >> t;

        v.push_back({s, t});
        vs.push_back(s);
    }
    sort(vs.begin(), vs.end());
    sort(v.begin(), v.end(), [](pi a, pi b){
        return a.x + a.y < b.x + b.y;
    });
    vector<Query> qr;
    for (int i = 0; i < q; i++){
        int x, y, z;
        cin >> x >> y >> z;

        qr.push_back({x, y, z, i});
    }
    sort(qr.begin(), qr.end(), [](Query a, Query b){
        return a.z < b.z;
    });
    int j = n - 1;

    vector<int> res(q, -1);
    for (int i = q - 1; i >= 0; i--){
        auto [x, y, z, indx] = qr[i];
        while (j >= 0 && v[j].x + v[j].y >= z){
            int pos = lower_bound(vs.begin(), vs.end(), v[j].x) - vs.begin();
            insert(def - v[j].x, def - v[j].y);
            j--;
        }
        int pos = upper_bound(vs.begin(), vs.end(), x - 1) - vs.begin();
        res[indx] = query(def - x, def - y);
    }
    for (int i = 0; i < q; i++)
        cout << res[i] << ' ';
}   

/*
-1 3 -1 1 0 -1

11 3 0 1 0 0

1 0 3 2
0 1 3 2 
*/

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (ifstream("input.txt").good()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    }

    int t;
    t = 1;
    
    while (t--){
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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