oj.uz

Submission #307927

# Submission time Handle Problem Language Result Execution time Memory
307927 2020-09-29T14:49:34 Z mohamedsobhi777 Examination (JOI19_examination) C++14
43 / 100
 1838 ms 125964 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp> 
/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/

#define I inline void 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using namespace __gnu_pbds; 

typedef tree<pii, null_type , less<pii> , rb_tree_tag , tree_order_statistics_node_update> indexed_set ; 

using ll = long long ; 
using ld = long double ; 


const int N = 1e5 + 7 , mod = 1e9 + 7 ; 
const int inf = N ; 
// How interesting!

int n , k; 
vector< pair<pii , pii> > v ; 
int ans[N] ; 
int A[N] , B[N] , S[N] ; 
int qA[N] , qB[N] , qS[N] ; 

vector<int> v1 , v2 ; 

void cmp(vector<int> &x){
        sort(x.begin() , x.end()) ; 
        x.erase(unique(x.begin() , x.end()) , x.end()) ; 
}

indexed_set mst[N] ; 
int t = 0 ; 

void add(int x , int y){
        for(;x < N ; x += x&-x)
                mst[x].insert({y , ++ t}) ; 
}

int upto(int x , int y){
        int ret = 0 ; 
        for(;x;x-=x&-x){
                int j = mst[x].order_of_key({y , -1}) ; 
                ret += (int) mst[x].size() - j ; 
        }
        return ret ; 
}

int get(int l ,int r , int x){
        return upto(r , x) - upto(l  - 1 ,x) ; 
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n >> k ; 
        for(int i = 0 ;i < n;i ++ ){
                cin >> A[i] >> B[i] ; 
                S[i] = A[i] + B[i] ; 
                v1.push_back(A[i]) ; 
                v2.push_back(B[i]) ; 
        }
        for(int i = 0 ;i < k ;i ++){
                cin >> qA[i] >> qB[i] >> qS[i] ; 
                v1.push_back(qA[i]) ; 
                v2.push_back(qB[i]) ; 
        }

        cmp(v1) ; 
        cmp(v2) ; 
        for(int i = 0 ;i < n;i ++){
                A[i] = lower_bound(v1.begin() , v1.end() , A[i]) - v1.begin() + 1 ; 
                B[i] = lower_bound(v2.begin() , v2.end() , B[i]) - v2.begin() + 1 ; 
        }

        for(int i = 0 ;i < k ; ++ i){
                qA[i] = lower_bound(v1.begin() , v1.end() , qA[i]) - v1.begin() + 1 ; 
                qB[i] = lower_bound(v2.begin() , v2.end() , qB[i]) - v2.begin() + 1 ;         
        }

        for(int i = 0 ;i < n;i ++ ){
                v.push_back({{-S[i] , - 1 } , {A[i] , B[i]} }) ; 
        }

        for(int i = 0 ;i < k;  ++ i){
                v.push_back({{-qS[i] , i } , {qA[i] , qB[i]} }) ; 
        }

        sort(v.begin() , v.end()) ; 

        vector< pii> aux ; 
        for(int i = 0 ;i < n + k ; ++ i){
                if(v[i].first.second < 0){
                        assert(v[i].second.first && v[i].second.second) ; 
                        add(v[i].second.first , v[i].second.second) ; 
                }
                else{
                        int ret = get(v[i].second.first , N - 1 , v[i].second.second) ; 
                        
                        ans[v[i].first.second] = ret ; 
                }

        }
        for(int i = 0 ;i < k ; ++ i)
                cout<< ans[i] <<"\n" ; 
        return 0 ; 
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 28 ms 12032 KB Output is correct
8 Correct 29 ms 12160 KB Output is correct
9 Correct 28 ms 12024 KB Output is correct
10 Correct 27 ms 12032 KB Output is correct
11 Correct 34 ms 12920 KB Output is correct
12 Correct 32 ms 12928 KB Output is correct
13 Correct 29 ms 12024 KB Output is correct
14 Correct 29 ms 12032 KB Output is correct
15 Correct 30 ms 12032 KB Output is correct
16 Correct 38 ms 13180 KB Output is correct
17 Correct 29 ms 12156 KB Output is correct
18 Correct 37 ms 13176 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 74328 KB Output is correct
2 Correct 1838 ms 76680 KB Output is correct
3 Correct 1831 ms 76552 KB Output is correct
4 Correct 1211 ms 75920 KB Output is correct
5 Correct 1240 ms 116488 KB Output is correct
6 Correct 1083 ms 115728 KB Output is correct
7 Correct 1396 ms 76556 KB Output is correct
8 Correct 1676 ms 76556 KB Output is correct
9 Correct 1202 ms 76300 KB Output is correct
10 Correct 1228 ms 125964 KB Output is correct
11 Correct 906 ms 75772 KB Output is correct
12 Correct 1610 ms 124908 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 74328 KB Output is correct
2 Correct 1838 ms 76680 KB Output is correct
3 Correct 1831 ms 76552 KB Output is correct
4 Correct 1211 ms 75920 KB Output is correct
5 Correct 1240 ms 116488 KB Output is correct
6 Correct 1083 ms 115728 KB Output is correct
7 Correct 1396 ms 76556 KB Output is correct
8 Correct 1676 ms 76556 KB Output is correct
9 Correct 1202 ms 76300 KB Output is correct
10 Correct 1228 ms 125964 KB Output is correct
11 Correct 906 ms 75772 KB Output is correct
12 Correct 1610 ms 124908 KB Output is correct
13 Correct 1545 ms 77048 KB Output is correct
14 Correct 1824 ms 77268 KB Output is correct
15 Correct 1816 ms 76832 KB Output is correct
16 Correct 935 ms 76292 KB Output is correct
17 Correct 1187 ms 116788 KB Output is correct
18 Correct 1108 ms 115708 KB Output is correct
19 Correct 1511 ms 77220 KB Output is correct
20 Correct 1652 ms 77244 KB Output is correct
21 Correct 1383 ms 76960 KB Output is correct
22 Correct 1238 ms 125956 KB Output is correct
23 Correct 1002 ms 75808 KB Output is correct
24 Correct 1643 ms 124892 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 28 ms 12032 KB Output is correct
8 Correct 29 ms 12160 KB Output is correct
9 Correct 28 ms 12024 KB Output is correct
10 Correct 27 ms 12032 KB Output is correct
11 Correct 34 ms 12920 KB Output is correct
12 Correct 32 ms 12928 KB Output is correct
13 Correct 29 ms 12024 KB Output is correct
14 Correct 29 ms 12032 KB Output is correct
15 Correct 30 ms 12032 KB Output is correct
16 Correct 38 ms 13180 KB Output is correct
17 Correct 29 ms 12156 KB Output is correct
18 Correct 37 ms 13176 KB Output is correct
19 Correct 1803 ms 74328 KB Output is correct
20 Correct 1838 ms 76680 KB Output is correct
21 Correct 1831 ms 76552 KB Output is correct
22 Correct 1211 ms 75920 KB Output is correct
23 Correct 1240 ms 116488 KB Output is correct
24 Correct 1083 ms 115728 KB Output is correct
25 Correct 1396 ms 76556 KB Output is correct
26 Correct 1676 ms 76556 KB Output is correct
27 Correct 1202 ms 76300 KB Output is correct
28 Correct 1228 ms 125964 KB Output is correct
29 Correct 906 ms 75772 KB Output is correct
30 Correct 1610 ms 124908 KB Output is correct
31 Correct 1545 ms 77048 KB Output is correct
32 Correct 1824 ms 77268 KB Output is correct
33 Correct 1816 ms 76832 KB Output is correct
34 Correct 935 ms 76292 KB Output is correct
35 Correct 1187 ms 116788 KB Output is correct
36 Correct 1108 ms 115708 KB Output is correct
37 Correct 1511 ms 77220 KB Output is correct
38 Correct 1652 ms 77244 KB Output is correct
39 Correct 1383 ms 76960 KB Output is correct
40 Correct 1238 ms 125956 KB Output is correct
41 Correct 1002 ms 75808 KB Output is correct
42 Correct 1643 ms 124892 KB Output is correct
43 Runtime error 226 ms 39136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -