oj.uz

Submission #331423

# Submission time Handle Problem Language Result Execution time Memory
331423 2020-11-28T12:39:27 Z EIMONIM Examination (JOI19_examination) C++14
2 / 100
 3000 ms 820792 KB 
#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 = 1e5+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]);
    }
    convs[INF] = convt[INF];
    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-1;
    MAXX = cnt, cnt = 0;
    for(auto &p:convt) p.second = cnt++;
    for(auto &p:convt) p.second = cnt - p.second-1;
    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;
            ans[i] = seg.query(0, a[i]+1, 0, b[i]+1, 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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 44 ms 15596 KB Output is correct
8 Correct 44 ms 15596 KB Output is correct
9 Correct 42 ms 15596 KB Output is correct
10 Correct 16 ms 3052 KB Output is correct
11 Correct 16 ms 2796 KB Output is correct
12 Correct 12 ms 512 KB Output is correct
13 Correct 44 ms 15724 KB Output is correct
14 Correct 47 ms 15608 KB Output is correct
15 Correct 45 ms 15776 KB Output is correct
16 Correct 12 ms 1016 KB Output is correct
17 Correct 12 ms 1260 KB Output is correct
18 Correct 9 ms 492 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3145 ms 820792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3145 ms 820792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 44 ms 15596 KB Output is correct
8 Correct 44 ms 15596 KB Output is correct
9 Correct 42 ms 15596 KB Output is correct
10 Correct 16 ms 3052 KB Output is correct
11 Correct 16 ms 2796 KB Output is correct
12 Correct 12 ms 512 KB Output is correct
13 Correct 44 ms 15724 KB Output is correct
14 Correct 47 ms 15608 KB Output is correct
15 Correct 45 ms 15776 KB Output is correct
16 Correct 12 ms 1016 KB Output is correct
17 Correct 12 ms 1260 KB Output is correct
18 Correct 9 ms 492 KB Output is correct
19 Execution timed out 3145 ms 820792 KB Time limit exceeded
20 Halted 0 ms 0 KB -