제출 #331420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331420		EIMONIM	Examination (JOI19_examination)	C++14	100 / 100	2783 ms	327020 KiB

examination

#include <bits/stdc++.h>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;

int MAXX = 0, MAXY = 0;
struct Node{
    int v=0;
    Node *lp=0, *rp=0;
    Node(){}
    void fix(){
        if (!lp) lp = new Node();
        if (!rp) rp = new Node();
    }
    void update(int i, int dx, int l, int r){
        if (r<=l) return ;
        if (l+1==r){
            v+=dx;
            return ;
        }
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,dx,l,mid);
        else rp->update(i,dx,mid,r);
        //cout<<"UPDATE1: "<<i<<" "<<l<<" "<<r<<(v - lp->v - rp->v)<<endl;
        v = lp->v + rp->v;
    }
    int query(int a, int b, int l, int r){
        if (a>r || b<l) return 0;
        //cout<<"QUERY1: "<<a<<" "<<v<<" "<<l<<" "<<r<<endl;
        if (a<=l && r<=b) return v;
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(a,b,l,mid);
        if (rp) res += rp->query(a,b,mid,r);
        return res;
    }
};
struct Node2d{
    Node seg;
    Node2d *lp=0, *rp=0;
    Node2d(){}
    void fix(){
        if (!lp) lp = new Node2d();
        if (!rp) rp = new Node2d();
    }
    void update(int i, int j, int dx, int l, int r){
        if (r<=l) return ;
        //cout<<"UPDATE: "<<i<<" "<<j<<" "<<l<<" "<<r<<endl;
        seg.update(j, dx, 0, MAXY);
        if (l+1==r) return ;
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,j,dx,l,mid);
        else rp->update(i,j,dx,mid,r);
    }
    int query(int ax, int bx, int ay, int by, int l, int r){
        if (ax>r || bx<l) return 0;
        if (ax<=l && r<=bx) {
            int v = seg.query(ay, by, 0, MAXY);
            //cout<<"QUERY: "<<ax<<" "<<ay<<" "<<l<<" "<<r<<" "<<v<<endl;
            return v;
        }
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(ax,bx,ay,by,l,mid);
        if (rp) res += rp->query(ax,bx,ay,by,mid,r);
        return res;
    }
};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
const int RANDOM =
    chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
  int operator()(int x) const { return x ^ RANDOM; }
};
struct sparsebit {
  const int MAX = 2e5+10;
  vector<gp_hash_table<int, int, chash>> fen;
  sparsebit(): fen(MAX+1){}
  int tot = 0;
  void add(int x, int y) {
    // debug("in upd");
    tot++;
    for (int i = x; i <= MAX; i += (i & -i)) {
      for (int j = y; j <= MAX; j += (j & -j)) {
        // debug(i, j, 1);
        // cnt++;
        fen[i][j] ++;
      }
    }
    // debug("out upd");
  }
 
  int qry(int x, int y) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i & -i)) {
      for (int j = y; j > 0; j -= (j & -j)) {
        // cnt++;
        ret += fen[i][j];
      }
    }
    return ret;
  }
 
  int qry(int a, int b, int c, int d) {
    // debug("in big qry");
    int ret = tot;
    if (a) ret -= qry(a - 1, d);
    if (b) ret -= qry(c, b - 1);
    if (a && b) ret += qry(a - 1, b - 1);
    // debug("out big qry");
    return ret;
  }
 
  void init() { fen.resize(MAX + 1); }
};
bool cmp(pair<int, int> a, pair<int, int> b){
    return (a.first==b.first?a.second<b.second:a.first>b.first);
}
const int MAXN = 1e5 + 10;
int s[MAXN], t[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int ans[MAXN];
pair<int, int> vals[2*MAXN];
int32_t main(){
    ios_base::sync_with_stdio(false);
    int n,q; cin>>n>>q;
    map<int, int> convs, convt;
    loop(i,0,n){
        cin>>s[i]>>t[i];
        vals[i] = {s[i]+t[i], i};
        convs[s[i]];
        convt[t[i]];
        //MAXX = max(MAXX, s[i]);
        //MAXY = max(MAXY, t[i]);
    }
    loop(i,0,q){
        cin>>a[i]>>b[i]>>c[i];
        vals[i+n] = {c[i], n+i};
        //MAXX = max(MAXX, a[i]);
        //MAXY = max(MAXY, b[i]);
    }
    sort(vals, vals+n+q, cmp);
    //MAXX++, MAXY++;
    int cnt = 0;
    for(auto &p:convs) p.second = cnt++;
    for(auto &p:convs) p.second = cnt - p.second;
    MAXX = cnt;
    cnt = 0;
    for(auto &p:convt) p.second = cnt++;
    for(auto &p:convt) p.second = cnt - p.second;
    MAXY = cnt;
    loop(i,0,n) s[i] = convs[s[i]], t[i] = convt[t[i]];
    loop(i,0,q) a[i] = convs.lower_bound(a[i])->second, b[i] = convt.lower_bound(b[i])->second;
    //Node2d seg;
    sparsebit bit;
    loop(ind, 0, n+q){
        int i = vals[ind].second;
        //cout<<"VALS: "<<vals[ind].first<<" "<<i<<" "<<i-n<<endl;
        if (i<n){ // point
            //seg.update(s[i], t[i], 1, 0, MAXX);
            bit.add(s[i], t[i]);
        }
        else{ // query
            i-=n;
            //ams [i] = seg.query(a[i], MAXX, b[i], MAXY, 0, MAXX);
            ans[i] = bit.qry(a[i], b[i]);
        }
    }
    loop(i,0,q) cout<<ans[i]<<endl;
    return 0;
}
/*
color a
cls
g++ Examination.cpp -o a & a
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100





*/

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