Submission #918464

#	Time	Username	Problem	Language	Result	Execution time	Memory
918464		ShaShi	Examination (JOI19_examination)	C++17	100 / 100	1688 ms	58572 KiB

examination

#include <bits/stdc++.h>
#define int long long 
#define F first
#define S second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pb push_back
#define endl "\n"
 
 
using namespace std;
typedef long long ll;
 
const int MAXN = (int)3e5 + 7;
const int MOD = 999999893;
const int INF = (int)1e18 + 7;
const int SQ = 350;
 
 
int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, ans2;
int arr2[MAXN], res[MAXN], love[MAXN], N, sz[MAXN];
pair<int, pii> arr[MAXN];
vector<pair<int, pii> > vec[MAXN];
vector<pair<int, pii> > op;
vector<int> cmp;
vector<int> fen[MAXN], fcmp[MAXN];


inline int id(int n) {
    return lower_bound(all(cmp), n)-cmp.begin();
}


inline int B(int n) {
    return n/SQ;
}


inline void upd(int x, int ind) {
    for (x++; x<fen[ind].size(); x+=x&-x) fen[ind][x]++;
}


inline int _get(int x, int ind) {
    int res = 0;
    for (x++; x>0; x-=x&-x) res += fen[ind][x];
    return res;
}


inline void add(int n, int ind) {
    // cout << "++ " << ind << " " << lower_bound(all(fcmp[ind]), n)-fcmp[ind].begin() << endl;
    sz[ind]++; upd(lower_bound(all(fcmp[ind]), n)-fcmp[ind].begin(), ind);
}


inline int get(int x, int ind) {
    return sz[ind]-_get(lower_bound(all(fcmp[ind]), x)-fcmp[ind].begin()-1, ind);
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

    cin >> n >> q;
    
    for (int i=0; i<n; i++) {
        cin >> arr[i].S.F >> arr[i].S.S;
        arr[i].F = arr[i].S.F+arr[i].S.S; cmp.pb(arr[i].S.F);
    }

    sort(all(cmp)); cmp.resize(unique(all(cmp))-cmp.begin()); N = cmp.size();
    arr[n] = mp(INF, mp(INF, INF)); sort(arr, arr+n+1);

    for (int i=0; i<q; i++) {
        cin >> u >> v >> w;

        tmp = lower_bound(arr, arr+n+1, mp(w, mp(-1ll, -1ll)))-arr;

        if (tmp == n) continue;
        vec[tmp].pb(mp(i, mp(u, v)));
    }

    for (int i=n-1; i>=0; i--) {
        op.pb(mp(-1, arr[i].S));

        for (auto cur:vec[i]) op.pb(cur);
    }


    for (int i=0; i<op.size(); i++) {
        u = id(op[i].S.F); v = op[i].S.S;

        if (op[i].F == -1) fcmp[u].pb(v), fcmp[N+B(u)].pb(v);
    }

    for (int i=0; i<N+SQ; i++) {
        sort(all(fcmp[i])); fcmp[i].pb(INF); fcmp[i].resize(unique(all(fcmp[i]))-fcmp[i].begin());
        fen[i].resize(fcmp[i].size()+2); fill(all(fen[i]), 0);
    }

    for (int i=0; i<op.size(); i++) {
        u = id(op[i].S.F); v = op[i].S.S;

        if (op[i].F == -1) {
            // cout << "+ " << u << " " << v << " " << endl;

            add(v, u); add(v, N+B(u));
        } else {
            // cout << "? " << u << " " << v << " -> " << op[i].F << endl;

            ans = 0;

            while (u < N && u%SQ) ans += get(v, u), u++;
            while (u < N && B(u) <= B(N-1)) ans += get(v, N+B(u)), u += SQ;

            res[op[i].F] = ans;
        }
    }


    for (int i=0; i<q; i++) {
        // cout << "!";
        cout << res[i] << endl;
    }



    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void upd(long long int, long long int)':
examination.cpp:42:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (x++; x<fen[ind].size(); x+=x&-x) fen[ind][x]++;
      |               ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int32_t main()':
examination.cpp:93:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i=0; i<op.size(); i++) {
      |                   ~^~~~~~~~~~
examination.cpp:104:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for (int i=0; i<op.size(); i++) {
      |                   ~^~~~~~~~~~

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