oj.uz

Submission #167199

# Submission time Handle Problem Language Result Execution time Memory
167199 2019-12-06T13:03:57 Z jh05013 Examination (JOI19_examination) C++17
2 / 100
 3000 ms 279224 KB 
#include <bits/stdc++.h>
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}

template <typename T>
struct Compress{
    int n; vector<T> arr;
    void add(T x){arr.push_back(x); n++;}
    void init(){sort(entire(arr)), arr.erase(unique(entire(arr)), arr.end());}
    int lb(T x){return lower_bound(entire(arr), x) - arr.begin();}
    int ub(T x){return upper_bound(entire(arr), x) - arr.begin();}
};

template <typename T>
struct Fenwick2d{
    int n, m;
    vector<unordered_map<int, T>> arr;
    Fenwick2d(int N, int M): n(N), m(M), arr(n) {}
    void update(int i, int j, T val){
        for(; i<n; i|=i+1) for(int p=j; p<m; p|=p+1) 
            arr[i][p]+= val;
    }
    T getsum(int i, int j){
        T res = 0;
        for(; i>=0; i=(i&(i+1))-1) for(int p=j; p>0; p=(p&(p+1))-1)
            res+= arr[i][p];
        return res;
    }
};

int main(){OJize();
    int n, q; cin>>n>>q;
    Compress<int> CX, CY;
    vector<tuple<int,int,int>> stu;
    vector<tuple<int,int,int,int>> query;
    for(int i=0; i<n; i++){
        int x,y; cin>>x>>y;
        stu.push_back({-x-y,x,y});
        CX.add(x), CY.add(y);
    }
    CX.init(), CY.init();
    sort(entire(stu));
    for(int i=0; i<q; i++){
        int x,y,z; cin>>x>>y>>z;
        query.push_back({-z,CX.lb(x),CY.lb(y),i});
    }
    sort(entire(query));

    vector<int> ans(q);
    Fenwick2d<int> F(n+2, n+2);
    int ptr = 0;
    for(auto [mz,x,y,i]: query){
        while(ptr<n){
            auto [mxyp, xp, yp] = stu[ptr];
            if(mxyp > mz) break;
            F.update(n-CX.lb(xp), n-CY.lb(yp), 1);
            ptr++;
        }
        ans[i] = F.getsum(n-x, n-y);
    }
    for(int x: ans) cout<<x<<'\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 47 ms 5624 KB Output is correct
8 Correct 44 ms 5624 KB Output is correct
9 Correct 46 ms 5624 KB Output is correct
10 Correct 16 ms 2040 KB Output is correct
11 Correct 17 ms 2040 KB Output is correct
12 Correct 9 ms 764 KB Output is correct
13 Correct 39 ms 5624 KB Output is correct
14 Correct 41 ms 5624 KB Output is correct
15 Correct 40 ms 5624 KB Output is correct
16 Correct 12 ms 1656 KB Output is correct
17 Correct 13 ms 1784 KB Output is correct
18 Correct 8 ms 764 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3102 ms 279224 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 3102 ms 279224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 47 ms 5624 KB Output is correct
8 Correct 44 ms 5624 KB Output is correct
9 Correct 46 ms 5624 KB Output is correct
10 Correct 16 ms 2040 KB Output is correct
11 Correct 17 ms 2040 KB Output is correct
12 Correct 9 ms 764 KB Output is correct
13 Correct 39 ms 5624 KB Output is correct
14 Correct 41 ms 5624 KB Output is correct
15 Correct 40 ms 5624 KB Output is correct
16 Correct 12 ms 1656 KB Output is correct
17 Correct 13 ms 1784 KB Output is correct
18 Correct 8 ms 764 KB Output is correct
19 Execution timed out 3102 ms 279224 KB Time limit exceeded
20 Halted 0 ms 0 KB -