oj.uz

Submission #290593

# Submission time Handle Problem Language Result Execution time Memory
290593 2020-09-04T06:00:38 Z davooddkareshki Examination (JOI19_examination) C++17
43 / 100
 3000 ms 385624 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<   long long,
                null_type,
                less_equal<long long>,
                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: '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]
  102 |             while(ptr < X.size())
      |                   ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 239888 KB Output is correct
2 Correct 242 ms 239864 KB Output is correct
3 Correct 235 ms 239788 KB Output is correct
4 Correct 232 ms 239864 KB Output is correct
5 Correct 238 ms 239992 KB Output is correct
6 Correct 234 ms 239864 KB Output is correct
7 Correct 256 ms 243224 KB Output is correct
8 Correct 254 ms 243188 KB Output is correct
9 Correct 265 ms 243360 KB Output is correct
10 Correct 261 ms 243316 KB Output is correct
11 Correct 262 ms 243188 KB Output is correct
12 Correct 245 ms 241396 KB Output is correct
13 Correct 251 ms 243444 KB Output is correct
14 Correct 254 ms 243192 KB Output is correct
15 Correct 258 ms 243316 KB Output is correct
16 Correct 251 ms 243060 KB Output is correct
17 Correct 280 ms 243060 KB Output is correct
18 Correct 242 ms 240888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2740 ms 368616 KB Output is correct
2 Correct 2712 ms 368636 KB Output is correct
3 Correct 2737 ms 368872 KB Output is correct
4 Correct 1688 ms 365152 KB Output is correct
5 Correct 1665 ms 365800 KB Output is correct
6 Correct 677 ms 288884 KB Output is correct
7 Correct 2762 ms 368576 KB Output is correct
8 Correct 2613 ms 368800 KB Output is correct
9 Correct 2360 ms 368356 KB Output is correct
10 Correct 1446 ms 367592 KB Output is correct
11 Correct 1436 ms 364260 KB Output is correct
12 Correct 540 ms 272484 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2740 ms 368616 KB Output is correct
2 Correct 2712 ms 368636 KB Output is correct
3 Correct 2737 ms 368872 KB Output is correct
4 Correct 1688 ms 365152 KB Output is correct
5 Correct 1665 ms 365800 KB Output is correct
6 Correct 677 ms 288884 KB Output is correct
7 Correct 2762 ms 368576 KB Output is correct
8 Correct 2613 ms 368800 KB Output is correct
9 Correct 2360 ms 368356 KB Output is correct
10 Correct 1446 ms 367592 KB Output is correct
11 Correct 1436 ms 364260 KB Output is correct
12 Correct 540 ms 272484 KB Output is correct
13 Correct 2635 ms 371948 KB Output is correct
14 Correct 2860 ms 370276 KB Output is correct
15 Correct 2726 ms 368612 KB Output is correct
16 Correct 1616 ms 366668 KB Output is correct
17 Correct 1478 ms 367208 KB Output is correct
18 Correct 663 ms 289512 KB Output is correct
19 Correct 2523 ms 372072 KB Output is correct
20 Correct 2698 ms 370960 KB Output is correct
21 Correct 2550 ms 371816 KB Output is correct
22 Correct 1465 ms 367432 KB Output is correct
23 Correct 1418 ms 364136 KB Output is correct
24 Correct 538 ms 272488 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 239888 KB Output is correct
2 Correct 242 ms 239864 KB Output is correct
3 Correct 235 ms 239788 KB Output is correct
4 Correct 232 ms 239864 KB Output is correct
5 Correct 238 ms 239992 KB Output is correct
6 Correct 234 ms 239864 KB Output is correct
7 Correct 256 ms 243224 KB Output is correct
8 Correct 254 ms 243188 KB Output is correct
9 Correct 265 ms 243360 KB Output is correct
10 Correct 261 ms 243316 KB Output is correct
11 Correct 262 ms 243188 KB Output is correct
12 Correct 245 ms 241396 KB Output is correct
13 Correct 251 ms 243444 KB Output is correct
14 Correct 254 ms 243192 KB Output is correct
15 Correct 258 ms 243316 KB Output is correct
16 Correct 251 ms 243060 KB Output is correct
17 Correct 280 ms 243060 KB Output is correct
18 Correct 242 ms 240888 KB Output is correct
19 Correct 2740 ms 368616 KB Output is correct
20 Correct 2712 ms 368636 KB Output is correct
21 Correct 2737 ms 368872 KB Output is correct
22 Correct 1688 ms 365152 KB Output is correct
23 Correct 1665 ms 365800 KB Output is correct
24 Correct 677 ms 288884 KB Output is correct
25 Correct 2762 ms 368576 KB Output is correct
26 Correct 2613 ms 368800 KB Output is correct
27 Correct 2360 ms 368356 KB Output is correct
28 Correct 1446 ms 367592 KB Output is correct
29 Correct 1436 ms 364260 KB Output is correct
30 Correct 540 ms 272484 KB Output is correct
31 Correct 2635 ms 371948 KB Output is correct
32 Correct 2860 ms 370276 KB Output is correct
33 Correct 2726 ms 368612 KB Output is correct
34 Correct 1616 ms 366668 KB Output is correct
35 Correct 1478 ms 367208 KB Output is correct
36 Correct 663 ms 289512 KB Output is correct
37 Correct 2523 ms 372072 KB Output is correct
38 Correct 2698 ms 370960 KB Output is correct
39 Correct 2550 ms 371816 KB Output is correct
40 Correct 1465 ms 367432 KB Output is correct
41 Correct 1418 ms 364136 KB Output is correct
42 Correct 538 ms 272488 KB Output is correct
43 Correct 2746 ms 385624 KB Output is correct
44 Correct 2739 ms 385512 KB Output is correct
45 Execution timed out 3015 ms 385376 KB Time limit exceeded
46 Halted 0 ms 0 KB -