oj.uz

Submission #290594

# Submission time Handle Problem Language Result Execution time Memory
290594 2020-09-04T06:02:59 Z davooddkareshki Examination (JOI19_examination) C++17
100 / 100
 2917 ms 311288 KB 
#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<   int,
                null_type,
                less_equal<int>,
                rb_tree_tag,
                tree_order_statistics_node_update>
ordered_multiset;

typedef long long ll;

//#define int long long
#define F first
#define S second
#define mpr make_pair
#define pii pair<int,int>

const int maxn = 6e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;

int n, m;
ordered_multiset seg[maxn<<2];

void add(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
    seg[v].insert(val);
    if(tl == tr) return;

    int tm = (tl + tr) >> 1;
    if(pos <= tm) add(pos, val, v<<1, tl, tm);
    else          add(pos, val, v<<1|1, tm+1, tr);
}

int qu(int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
    if(l > r) return 0;
    if(tl == l && tr == r)
    {
        int x = seg[v].order_of_key(val);
        int y = seg[v].size();
        return y-x;
    }

    int tm = (tl + tr) >> 1;
    return qu(l, min(tm,r), val, v<<1, tl, tm) +
            qu(max(tm+1,l), r, val, v<<1|1, tm+1, tr);
}

vector<int> ve;
int mp(int x) {return upper_bound(ve.begin(), ve.end(), x) - ve.begin();}
vector<pair<int,pii>> X;
int A[maxn], B[maxn], C[maxn];
vector<pair<pii,int>> Q[maxn];
int ans[maxn];

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

    int q; cin>> m >> q;
    for(int i = 1, a, b; i <= m; i++)
    {
        cin>> a >> b;
        X.push_back({a+b,{a,b}});
        ve.push_back(a+b); ve.push_back(a); ve.push_back(b);
    }
    sort(X.begin(), X.end());

    for(int i = 1; i <= q; i++)
    {
        cin>> A[i] >> B[i] >> C[i];
        ve.push_back(A[i]); ve.push_back(B[i]); ve.push_back(C[i]);
    }
    sort(ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());

    for(int i = 1; i <= q; i++)
    {
        A[i] = mp(A[i]); B[i] = mp(B[i]); C[i] = mp(C[i]);
        Q[C[i]].push_back({{A[i],B[i]},i});
    }
    for(auto &x : X)
    {
        x.F = mp(x.F);
        x.S.F = mp(x.S.F);
        x.S.S = mp(x.S.S);
    }

    n = ve.size();
    reverse(X.begin(), X.end());

    int ptr = 0;
    for(int i = maxn-1; i >= 0; i--)
        if(Q[i].size())
        {
           // cout<< i <<"\n";
            while(ptr < X.size())
                if(X[ptr].F >= i)
                {
               //     cout<< X[ptr].F <<" "<< X[ptr].S.F <<" "<< X[ptr].S.S <<"\n";
                    add(X[ptr].S.F, X[ptr].S.S);
                    ptr++;
                }
                else break;

         //   cout<<"\n";
            for(auto x : Q[i])
            {
                int A = x.F.F, B = x.F.S, id = x.S;
         //       cout<< id <<" "<< A <<" "<< B <<"\n";
                ans[id] = qu(A, n, B);
            }
        //    cout<<"\n";
        }
    for(int i = 1; i <= q; i++) cout<< ans[i] <<"\n";
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             while(ptr < X.size())
      |                   ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 202364 KB Output is correct
2 Correct 208 ms 202364 KB Output is correct
3 Correct 209 ms 202360 KB Output is correct
4 Correct 212 ms 202360 KB Output is correct
5 Correct 209 ms 202424 KB Output is correct
6 Correct 207 ms 202360 KB Output is correct
7 Correct 226 ms 204664 KB Output is correct
8 Correct 230 ms 204924 KB Output is correct
9 Correct 246 ms 204664 KB Output is correct
10 Correct 227 ms 204792 KB Output is correct
11 Correct 229 ms 204664 KB Output is correct
12 Correct 213 ms 203256 KB Output is correct
13 Correct 232 ms 204664 KB Output is correct
14 Correct 226 ms 204664 KB Output is correct
15 Correct 228 ms 204664 KB Output is correct
16 Correct 232 ms 204572 KB Output is correct
17 Correct 225 ms 204520 KB Output is correct
18 Correct 211 ms 203128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2645 ms 294128 KB Output is correct
2 Correct 2645 ms 294396 KB Output is correct
3 Correct 2625 ms 294092 KB Output is correct
4 Correct 1631 ms 291952 KB Output is correct
5 Correct 1482 ms 292816 KB Output is correct
6 Correct 594 ms 235412 KB Output is correct
7 Correct 2581 ms 294080 KB Output is correct
8 Correct 2508 ms 294152 KB Output is correct
9 Correct 2291 ms 293732 KB Output is correct
10 Correct 1286 ms 293768 KB Output is correct
11 Correct 1347 ms 291316 KB Output is correct
12 Correct 463 ms 222964 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2645 ms 294128 KB Output is correct
2 Correct 2645 ms 294396 KB Output is correct
3 Correct 2625 ms 294092 KB Output is correct
4 Correct 1631 ms 291952 KB Output is correct
5 Correct 1482 ms 292816 KB Output is correct
6 Correct 594 ms 235412 KB Output is correct
7 Correct 2581 ms 294080 KB Output is correct
8 Correct 2508 ms 294152 KB Output is correct
9 Correct 2291 ms 293732 KB Output is correct
10 Correct 1286 ms 293768 KB Output is correct
11 Correct 1347 ms 291316 KB Output is correct
12 Correct 463 ms 222964 KB Output is correct
13 Correct 2559 ms 297020 KB Output is correct
14 Correct 2760 ms 295300 KB Output is correct
15 Correct 2647 ms 294004 KB Output is correct
16 Correct 1505 ms 293236 KB Output is correct
17 Correct 1467 ms 293620 KB Output is correct
18 Correct 598 ms 235768 KB Output is correct
19 Correct 2543 ms 297008 KB Output is correct
20 Correct 2618 ms 296216 KB Output is correct
21 Correct 2404 ms 296812 KB Output is correct
22 Correct 1304 ms 293496 KB Output is correct
23 Correct 1418 ms 291188 KB Output is correct
24 Correct 469 ms 222968 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 202364 KB Output is correct
2 Correct 208 ms 202364 KB Output is correct
3 Correct 209 ms 202360 KB Output is correct
4 Correct 212 ms 202360 KB Output is correct
5 Correct 209 ms 202424 KB Output is correct
6 Correct 207 ms 202360 KB Output is correct
7 Correct 226 ms 204664 KB Output is correct
8 Correct 230 ms 204924 KB Output is correct
9 Correct 246 ms 204664 KB Output is correct
10 Correct 227 ms 204792 KB Output is correct
11 Correct 229 ms 204664 KB Output is correct
12 Correct 213 ms 203256 KB Output is correct
13 Correct 232 ms 204664 KB Output is correct
14 Correct 226 ms 204664 KB Output is correct
15 Correct 228 ms 204664 KB Output is correct
16 Correct 232 ms 204572 KB Output is correct
17 Correct 225 ms 204520 KB Output is correct
18 Correct 211 ms 203128 KB Output is correct
19 Correct 2645 ms 294128 KB Output is correct
20 Correct 2645 ms 294396 KB Output is correct
21 Correct 2625 ms 294092 KB Output is correct
22 Correct 1631 ms 291952 KB Output is correct
23 Correct 1482 ms 292816 KB Output is correct
24 Correct 594 ms 235412 KB Output is correct
25 Correct 2581 ms 294080 KB Output is correct
26 Correct 2508 ms 294152 KB Output is correct
27 Correct 2291 ms 293732 KB Output is correct
28 Correct 1286 ms 293768 KB Output is correct
29 Correct 1347 ms 291316 KB Output is correct
30 Correct 463 ms 222964 KB Output is correct
31 Correct 2559 ms 297020 KB Output is correct
32 Correct 2760 ms 295300 KB Output is correct
33 Correct 2647 ms 294004 KB Output is correct
34 Correct 1505 ms 293236 KB Output is correct
35 Correct 1467 ms 293620 KB Output is correct
36 Correct 598 ms 235768 KB Output is correct
37 Correct 2543 ms 297008 KB Output is correct
38 Correct 2618 ms 296216 KB Output is correct
39 Correct 2404 ms 296812 KB Output is correct
40 Correct 1304 ms 293496 KB Output is correct
41 Correct 1418 ms 291188 KB Output is correct
42 Correct 469 ms 222968 KB Output is correct
43 Correct 2682 ms 306528 KB Output is correct
44 Correct 2690 ms 306404 KB Output is correct
45 Correct 2917 ms 306256 KB Output is correct
46 Correct 1622 ms 306808 KB Output is correct
47 Correct 1643 ms 307240 KB Output is correct
48 Correct 630 ms 242160 KB Output is correct
49 Correct 2683 ms 311284 KB Output is correct
50 Correct 2524 ms 311288 KB Output is correct
51 Correct 2427 ms 311172 KB Output is correct
52 Correct 2098 ms 308220 KB Output is correct
53 Correct 1381 ms 299308 KB Output is correct