Submission #290594

#	Time	Username	Problem	Language	Result	Execution time	Memory
290594		davooddkareshki	Examination (JOI19_examination)	C++17	100 / 100	2917 ms	311288 KiB

examination

#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 (stderr)

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57