oj.uz

Submission #126933

# Submission time Handle Problem Language Result Execution time Memory
126933 2019-07-08T16:07:45 Z MohamedAhmed04 Examination (JOI19_examination) C++14
41 / 100
 2214 ms 219148 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int , pair<int , int> > , null_type, less<pair<int , pair<int , int> > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1000005;

ordered_set bit[N];

void update(int x, int y , int idx)
{
	for(int i = x; i < N; i += i & -i)
		bit[i].insert({y, {x , idx}});
}
int query(int x, int y)
{
	int ans = 0;
	for(int i = x; i > 0; i -= i & -i)
    {
        ans += bit[i].order_of_key({y+1, {0 , -1}});
    }
	return ans;
}
/*int query(int x , int y)
{
    int ans = 0 ;
    while(x > 0)
    {
        int y1 = y ;
        while(y1 > 0)
        {
            ans += bit[{x , y1}] ;
            y1 -= (y1 & -y1) ;
        }
        x -= (x & -x) ;
    }
    return ans ;
}*/

int a[N], b[N] , ans[N];

int main()
{
    int n , q ;
    scanf("%d %d" , &n, &q) ;
    vector< pair<int , int> >vp ;
    vector< pair<int , pair<int , pair<int , int> > > >vp2 ;
    for(int i = 0 ; i < n ; ++i)
    {
        cin>>a[i]>>b[i] ;
        a[i] += 2 ;
        b[i] += 2 ;
        vp.push_back({a[i] , b[i]}) ;
    }
    for(int i = 0 ; i < q ; ++i)
    {
        int x , y , z ;
        cin>>x>>y>>z ;
        x += 2 ;
        y += 2 ;
        z += 4 ;
        vp2.push_back({x , {y , {z , i}}}) ;
        //cout<<query(N-1 , N-1 , z) - query(x-1 , N-1 , z) - query(N-1 , y-1 , z) + query(x-1 , y-1 , z)<<"\n";
    }
    sort(vp.begin() , vp.end()) ;
    reverse(vp.begin() , vp.end()) ;
    sort(vp2.begin() , vp2.end()) ;
    reverse(vp2.begin() , vp2.end()) ;
    int idx = 0 ;
    for(int i = 0 ; i < q ; ++i)
    {
        while(idx < n && vp[idx].first >= vp2[i].first)
        {
            update(vp[idx].second , vp[idx].first + vp[idx].second , idx) ;
            idx++ ;
        }
        int idxx = vp2[i].second.second.second ;
        int x = vp2[i].second.first , y = vp2[i].second.second.first ;
        ans[idxx] = query(N-1 , N-1) - query(x-1 , N-1) - query(N-1 , y-1) + query(x-1 , y-1) ;
    }
    for(int i = 0 ; i < q ; ++i)
        cout<<ans[i]<<"\n";
    return 0 ;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d" , &n, &q) ;
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 94328 KB Output is correct
2 Correct 125 ms 94328 KB Output is correct
3 Correct 122 ms 94328 KB Output is correct
4 Runtime error 231 ms 190552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1885 ms 175044 KB Output is correct
2 Correct 2005 ms 175320 KB Output is correct
3 Correct 1934 ms 174972 KB Output is correct
4 Correct 1693 ms 214012 KB Output is correct
5 Correct 1046 ms 174424 KB Output is correct
6 Correct 1445 ms 213484 KB Output is correct
7 Correct 1936 ms 175108 KB Output is correct
8 Correct 1644 ms 175212 KB Output is correct
9 Correct 1627 ms 175104 KB Output is correct
10 Correct 928 ms 174332 KB Output is correct
11 Correct 1694 ms 219088 KB Output is correct
12 Correct 2149 ms 218088 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1885 ms 175044 KB Output is correct
2 Correct 2005 ms 175320 KB Output is correct
3 Correct 1934 ms 174972 KB Output is correct
4 Correct 1693 ms 214012 KB Output is correct
5 Correct 1046 ms 174424 KB Output is correct
6 Correct 1445 ms 213484 KB Output is correct
7 Correct 1936 ms 175108 KB Output is correct
8 Correct 1644 ms 175212 KB Output is correct
9 Correct 1627 ms 175104 KB Output is correct
10 Correct 928 ms 174332 KB Output is correct
11 Correct 1694 ms 219088 KB Output is correct
12 Correct 2149 ms 218088 KB Output is correct
13 Correct 2012 ms 175584 KB Output is correct
14 Correct 1995 ms 175588 KB Output is correct
15 Correct 1819 ms 175208 KB Output is correct
16 Correct 1871 ms 214508 KB Output is correct
17 Correct 1137 ms 174828 KB Output is correct
18 Correct 1457 ms 213352 KB Output is correct
19 Correct 1959 ms 175684 KB Output is correct
20 Correct 1980 ms 175568 KB Output is correct
21 Correct 2150 ms 175660 KB Output is correct
22 Correct 956 ms 174320 KB Output is correct
23 Correct 1688 ms 219148 KB Output is correct
24 Correct 2214 ms 218112 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 94328 KB Output is correct
2 Correct 125 ms 94328 KB Output is correct
3 Correct 122 ms 94328 KB Output is correct
4 Runtime error 231 ms 190552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -