Submission #376091

#	Time	Username	Problem	Language	Result	Execution time	Memory
376091		souvenir_vayne	Examination (JOI19_examination)	C++14	100 / 100	766 ms	56148 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <chrono>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define fin cin
#define fout cout
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
#define all(x) x.begin(), x.end()
#define left vadia
#define lb lower_bound
#define right puta
using namespace std;
using namespace __gnu_pbds;
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str( ),"w",stdout);
}
typedef pair<ll, ll> pii;
typedef vector<vector<char>> mat;
typedef pair<int, string> pis;
const ll mod = 1e9+7, MAXN = 1e5;
typedef vector<int> vi;
typedef pair<int, pair<int, int>> piii;

struct qu {
    ll a, b, c;
};

vector<int> seg[2][4*MAXN];

void update(int u, int id, int l, int r, int i, ll x) {

    if(l > i or r < i)
        return;

    seg[id][u].pb(x);
    if(l == r)
        return;

    int mid = (l + r)/2;
    update(2*u, id, l, mid, i, x);
    update(2*u+1, id, mid+1, r, i, x);

    return;
}

int query(int u, int id, int l, int r, int lq, int rq, ll x) {
    if(l >= lq && r <= rq)
        return lower_bound(seg[id][u].begin(), seg[id][u].end(), x) - seg[id][u].begin();
    if(lq > r or rq < l)
        return 0;
    int mid = (l + r) >> 1;
    return query(2*u, id, l, mid, lq, rq, x) + query(2*u+1, id, mid+1, r, lq, rq, x);
}

int32_t main() {

    FAST;
    int n, Q;
    cin >> n >> Q;

    vector<pii> v(n), v2(n);
    vector<int> compress;

    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v[i].f = a + b, v[i].s = a;
        v2[i].f = a + b, v2[i].s = b;
    }

    sort(all(v));
    sort(all(v2));

    for(int i = 0; i < n; i++) {
        update(1, 0, 1, n, i+1, v[i].s);
        update(1, 1, 1, n, i+1, v2[i].s);
    }

    for(int i = 1; i < 4 * MAXN; i++) {
        sort(all(seg[0][i]));
        sort(all(seg[1][i]));
    }

    vector<qu> q(Q);

    for(int i = 0; i < Q; i++) {

        cin >> q[i].a >> q[i].b >> q[i].c;
        q[i].c = max(q[i].c, q[i].a + q[i].b);

        int ini = 0, mid, end = n, ans = n;

        while(ini <= end) {
            mid = (ini+end)>>1;
            if(v[mid].f >= q[i].c) {
                end = mid-1;
                ans = min(ans, mid);
            }
            else
                ini = mid+1;
        }

        mid = ans + 1;
        cout << n - mid + 1 - (query(1, 0, 1, n, mid, n, q[i].a) + query(1, 1, 1, n, mid, n, q[i].b)) << endl;

    }



}

Compilation message (stderr)

examination.cpp: In function 'void setIO(std::string)':
examination.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((s+".out").c_str( ),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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