Submission #151581

#	Time	Username	Problem	Language	Result	Execution time	Memory
151581		2qbingxuan	Examination (JOI19_examination)	C++14	100 / 100	491 ms	18952 KiB

examination

//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \\#################\\
//   \\#################\\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define pb emplace_back
#define ff first
#define ss second
#define mid (l+(r-l>>1))

using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
template <typename T> using rkt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-9;
constexpr ll N = 200800, INF = 1e18, MOD = 998244353, K = 102425;
constexpr inline ll cdiv(ll x, ll m) { return (x+m-1)/m; } // ceiling divide, x/m for flooring divide
template <typename T> void M(T &x, ll m = MOD){x%=m; if(x<0) x+=m;}

struct Query{
    ll k,x,y,z;
} Q[N];
ll v[N],b[N],ans[N];
void add(int p, ll d) {
    for(; p < N; p += p&-p) b[p] += d;
}
ll qry(int p) {
    ll r = 0;
    for(; p > 0; p -= p&-p) r += b[p];
    return r;
}
void merges(int l,int m,int r) {
    auto cmp = [](int a, int b){return Q[a].y != Q[b].y ? Q[a].y < Q[b].y : a<b;};
    vector<int> tmp;
    for(int i = l, j = m; i<m || j<r; ) {
        if(j==r || (i<m && cmp(v[i],v[j]))) {
            auto &q = Q[v[i]];
            if(q.k == 0) add(q.z,1);
            tmp.pb(v[i++]);
        }else {
            auto &q = Q[v[j]];
            if(q.k == 1) ans[v[j]] += qry(q.z);
            tmp.pb(v[j++]);
        }
    }
    for(int i = l; i < m; i++) if(Q[v[i]].k == 0) add(Q[v[i]].z,-1);
    for(int i = l; i < r; i++) v[i] = tmp[i-l];
}
void CDQ(int l, int r) {
    if(l+1 == r) return;
    CDQ(l,mid), CDQ(mid,r);
    merges(l,mid,r);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    ll n,q,x,y,z,p = 0;
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        cin >> x >> y, z = x+y;
        Q[p++] = {0,-x,-y,-z};
    }
    for(int i = 0; i < q; i++) {
        cin >> x >> y >> z;
        Q[p++] = {1,-x,-y,-z};
    }
    vector<ll> u;
    for(int i = 0; i < p; i++) u.pb(Q[i].z);
    sort(all(u)), u.erase(unique(all(u)),u.end());
    for(int i = 0; i < p; i++) Q[i].z = get_pos(u,Q[i].z)+1;
    iota(v,v+p,0);
    sort(v,v+p,[](int a, int b){return Q[a].x!=Q[b].x ? Q[a].x < Q[b].x : a<b;});
    CDQ(0,p);
    for(int i = 0; i < q; i++) cout << ans[i+n] << '\n';
    /*
    for(int i = 0; i < p; i++) if(Q[i].k == 1) {
        auto &p = Q[i];
        int ans = 0;
        for(int j = 0; j < i; j++) {
            auto &q = Q[j];
            if(q.k == 0 && q.x >= p.x && q.y >= p.y && q.z >= p.z) ans++;
        }
        cout << ans << '\n';
    }
    */
}

Compilation message (stderr)

examination.cpp:9:1: warning: multi-line comment [-Wcomment]
 //  \\#################\\
 ^
examination.cpp:16:0: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
 #pragma loop_opt(on)
 
examination.cpp: In function 'void CDQ(int, int)':
examination.cpp:27:18: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
 #define mid (l+(r-l>>1))
                 ~^~
examination.cpp:71:11: note: in expansion of macro 'mid'
     CDQ(l,mid), CDQ(mid,r);
           ^~~
examination.cpp:27:18: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
 #define mid (l+(r-l>>1))
                 ~^~
examination.cpp:71:21: note: in expansion of macro 'mid'
     CDQ(l,mid), CDQ(mid,r);
                     ^~~
examination.cpp:27:18: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
 #define mid (l+(r-l>>1))
                 ~^~
examination.cpp:72:14: note: in expansion of macro 'mid'
     merges(l,mid,r);
              ^~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57