Submission #1339539

#TimeUsernameProblemLanguageResultExecution timeMemory
1339539shiba_ensureExamination (JOI19_examination)C++20
0 / 100
368 ms9432 KiB
#include <bits/stdc++.h>
#include <stdio.h>

#define __Shibae__      signed main()
#define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fiopen(Path)    freopen(Path".INP", "r", stdin); freopen(Path".OUT", "w", stdout);
#define fipen(Path)     freopen(Path".INP", "r", stdin);
#define sz(s)           (int)s.size()
#define all(x)          x.begin(), x.end()
#define maxHeap         priority_queue<int>
#define minHeap         priority_queue<int, vector<int>, greater<int>>
#define getBit(x, k)    (((x) >> (k)) & 1)
#define MASK(i)         (1LL << (i))
#define SQR(x)          (1LL * ((x) * (x)))
#define db              double
#define ld              long double
#define ui              unsigned int
#define ll              long long
#define ii              pair<int, int>
#define pli             pair<ll, int>
#define pil             pair<int, ll>
#define pll             pair<ll, ll>
#define fi              first
#define se              second

#define FOR(i, a, b)    for(int i = a, _b = b; i <= _b; i += 1)
#define FOD(i, a, b)    for(int i = a, _b = b; i >= _b; i -= 1)
#define REP(i, a)       for(int i = 0, _a = a; i < _a; i++)
#define pb              push_back
#define fau(u, a)       for(auto &u : a)
#define debug           return cout << "debug", void();

using namespace std;

const ll mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);
const int MAX = 5e5+5;
 
const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(ll l, ll r) 
{
    return uniform_int_distribution<ll>(l, r)(rd);
}

template<class SHIBA, class ENGINE>
    bool minimize(SHIBA &x, const ENGINE y)
    {
        if(x > y)
        {
            x = y;
            return true;
        } 
        else return false;
    }
template<class SHIBA, class ENGINE>
    bool maximize(SHIBA &x, const ENGINE y)
    {
        if(x < y)
        {
            x = y;
            return true;
        }
        else return false;
    }


/* Template by: Nguyen Nhat Anh from Luong Van Chanh High School for the gifted */
/* From Min Tuoi with love */
        /**       TRY HARD        **/
        /**          ORZ          **/

/* -----------------[ MAIN CODE ]----------------- */

struct Node
{
    int x, y, z, type, id;

    bool operator < (const Node &b) const
    {
        if (x != b.x) return x > b.x;
        return type > b.type;
    }
};

int N;
int n, q;
Node a[MAX];
int bit[MAX];
int res[MAX];

void update(int i, int k)
{
    for (; i; i -= i & -i) bit[i] += k;
}

int get(int i)
{
    int res = 0;
    for (; i <= N; i += i & -i) res += bit[i];
    return res;
}

vector<int> ax, ay, az;

void input()
{
    cin >> n >> q;

    FOR(i, 1, n)
    {
        cin >> a[i].x >> a[i].y;
        a[i].z = a[i].x + a[i].y;
        a[i].type = 1;

        ax.pb(a[i].x);
        ay.pb(a[i].y);
        az.pb(a[i].z);
    }

    FOR(i, n+1, n+q)
    {
        cin >> a[i].x >> a[i].y >> a[i].z;
        a[i].id = i-n;

        ax.pb(a[i].x);
        ay.pb(a[i].y);
        az.pb(a[i].z);
    }
}

void dnc(int l, int r)
{
    if (l == r) return;

    int m = l + r >> 1;

    vector<int> idx(r-l+1);
    iota(all(idx), l);

    sort(all(idx), [&](const int &i, const int &j){
        return a[i].y > a[j].y;
    });

    vector<int> tmp;

    fau(i, idx)
    {
        if (i <= m && a[i].type == 1) 
        {
            update(a[i].z, 1);
            tmp.pb(a[i].z);
        }
        else if (i > m && a[i].type == 0) res[a[i].id] += get(a[i].z);
    }

    fau(x, tmp) update(x, -1);

    dnc(l, m);
    dnc(m+1, r);
}

void solve()
{
    sort(all(ax));
    ax.resize(unique(all(ax)) - ax.begin());
    sort(all(ay));
    ay.resize(unique(all(ay)) - ay.begin());
    sort(all(az));
    az.resize(unique(all(az)) - az.begin());

    FOR(i, 1, n+q)
    {
        a[i].x = lower_bound(all(ax), a[i].x) - ax.begin() + 1;
        a[i].y = lower_bound(all(ay), a[i].y) - ay.begin() + 1;
        a[i].z = lower_bound(all(az), a[i].z) - az.begin() + 1;
    }

    sort(a+1, a+1+n+q);
    N = az.size();
    dnc(1, n+q);

    FOR(i, 1, q) cout << res[i] << "\n";
}

__Shibae__
{
    IOS

    const bool multitest = 0;
    int tt = 1; if(multitest) cin >> tt;
 
    while( tt-- ){
        input();
        solve();
        if(tt) cout << "\n";
    }
 
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...