oj.uz

Submission #918464

# Submission time Handle Problem Language Result Execution time Memory
918464 2024-01-29T21:14:55 Z ShaShi Examination (JOI19_examination) C++17
100 / 100
 1688 ms 58572 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 8 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 16 ms 30108 KB Output is correct
8 Correct 16 ms 29980 KB Output is correct
9 Correct 17 ms 29984 KB Output is correct
10 Correct 16 ms 29980 KB Output is correct
11 Correct 13 ms 29984 KB Output is correct
12 Correct 9 ms 29728 KB Output is correct
13 Correct 16 ms 30044 KB Output is correct
14 Correct 16 ms 30044 KB Output is correct
15 Correct 16 ms 30044 KB Output is correct
16 Correct 10 ms 29784 KB Output is correct
17 Correct 13 ms 29980 KB Output is correct
18 Correct 9 ms 29532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 52740 KB Output is correct
2 Correct 975 ms 52540 KB Output is correct
3 Correct 945 ms 52876 KB Output is correct
4 Correct 348 ms 51328 KB Output is correct
5 Correct 139 ms 47380 KB Output is correct
6 Correct 66 ms 46660 KB Output is correct
7 Correct 1419 ms 53828 KB Output is correct
8 Correct 631 ms 54068 KB Output is correct
9 Correct 949 ms 53564 KB Output is correct
10 Correct 79 ms 48352 KB Output is correct
11 Correct 250 ms 52384 KB Output is correct
12 Correct 49 ms 45880 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 52740 KB Output is correct
2 Correct 975 ms 52540 KB Output is correct
3 Correct 945 ms 52876 KB Output is correct
4 Correct 348 ms 51328 KB Output is correct
5 Correct 139 ms 47380 KB Output is correct
6 Correct 66 ms 46660 KB Output is correct
7 Correct 1419 ms 53828 KB Output is correct
8 Correct 631 ms 54068 KB Output is correct
9 Correct 949 ms 53564 KB Output is correct
10 Correct 79 ms 48352 KB Output is correct
11 Correct 250 ms 52384 KB Output is correct
12 Correct 49 ms 45880 KB Output is correct
13 Correct 995 ms 53836 KB Output is correct
14 Correct 974 ms 53824 KB Output is correct
15 Correct 952 ms 52484 KB Output is correct
16 Correct 395 ms 52420 KB Output is correct
17 Correct 168 ms 48372 KB Output is correct
18 Correct 65 ms 46168 KB Output is correct
19 Correct 994 ms 54948 KB Output is correct
20 Correct 1000 ms 53844 KB Output is correct
21 Correct 1142 ms 53800 KB Output is correct
22 Correct 76 ms 46500 KB Output is correct
23 Correct 250 ms 51776 KB Output is correct
24 Correct 47 ms 45472 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 8 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 16 ms 30108 KB Output is correct
8 Correct 16 ms 29980 KB Output is correct
9 Correct 17 ms 29984 KB Output is correct
10 Correct 16 ms 29980 KB Output is correct
11 Correct 13 ms 29984 KB Output is correct
12 Correct 9 ms 29728 KB Output is correct
13 Correct 16 ms 30044 KB Output is correct
14 Correct 16 ms 30044 KB Output is correct
15 Correct 16 ms 30044 KB Output is correct
16 Correct 10 ms 29784 KB Output is correct
17 Correct 13 ms 29980 KB Output is correct
18 Correct 9 ms 29532 KB Output is correct
19 Correct 950 ms 52740 KB Output is correct
20 Correct 975 ms 52540 KB Output is correct
21 Correct 945 ms 52876 KB Output is correct
22 Correct 348 ms 51328 KB Output is correct
23 Correct 139 ms 47380 KB Output is correct
24 Correct 66 ms 46660 KB Output is correct
25 Correct 1419 ms 53828 KB Output is correct
26 Correct 631 ms 54068 KB Output is correct
27 Correct 949 ms 53564 KB Output is correct
28 Correct 79 ms 48352 KB Output is correct
29 Correct 250 ms 52384 KB Output is correct
30 Correct 49 ms 45880 KB Output is correct
31 Correct 995 ms 53836 KB Output is correct
32 Correct 974 ms 53824 KB Output is correct
33 Correct 952 ms 52484 KB Output is correct
34 Correct 395 ms 52420 KB Output is correct
35 Correct 168 ms 48372 KB Output is correct
36 Correct 65 ms 46168 KB Output is correct
37 Correct 994 ms 54948 KB Output is correct
38 Correct 1000 ms 53844 KB Output is correct
39 Correct 1142 ms 53800 KB Output is correct
40 Correct 76 ms 46500 KB Output is correct
41 Correct 250 ms 51776 KB Output is correct
42 Correct 47 ms 45472 KB Output is correct
43 Correct 1203 ms 57692 KB Output is correct
44 Correct 1191 ms 57464 KB Output is correct
45 Correct 1172 ms 58336 KB Output is correct
46 Correct 406 ms 54712 KB Output is correct
47 Correct 161 ms 49668 KB Output is correct
48 Correct 60 ms 42732 KB Output is correct
49 Correct 1688 ms 58572 KB Output is correct
50 Correct 802 ms 55992 KB Output is correct
51 Correct 1177 ms 58328 KB Output is correct
52 Correct 105 ms 49588 KB Output is correct
53 Correct 285 ms 53072 KB Output is correct