oj.uz

Submission #126935

# Submission time Handle Problem Language Result Execution time Memory
126935 2019-07-08T16:09:00 Z MohamedAhmed04 Examination (JOI19_examination) C++14
41 / 100
 2102 ms 146020 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 = 300005;

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 38 ms 28536 KB Output is correct
2 Correct 39 ms 28536 KB Output is correct
3 Correct 40 ms 28652 KB Output is correct
4 Runtime error 83 ms 57592 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 1721 ms 100788 KB Output is correct
2 Correct 1703 ms 102216 KB Output is correct
3 Correct 1630 ms 101884 KB Output is correct
4 Correct 1609 ms 141292 KB Output is correct
5 Correct 903 ms 101456 KB Output is correct
6 Correct 1343 ms 141260 KB Output is correct
7 Correct 1731 ms 101620 KB Output is correct
8 Correct 1489 ms 101728 KB Output is correct
9 Correct 1440 ms 101604 KB Output is correct
10 Correct 773 ms 101400 KB Output is correct
11 Correct 1531 ms 146020 KB Output is correct
12 Correct 2102 ms 145764 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1721 ms 100788 KB Output is correct
2 Correct 1703 ms 102216 KB Output is correct
3 Correct 1630 ms 101884 KB Output is correct
4 Correct 1609 ms 141292 KB Output is correct
5 Correct 903 ms 101456 KB Output is correct
6 Correct 1343 ms 141260 KB Output is correct
7 Correct 1731 ms 101620 KB Output is correct
8 Correct 1489 ms 101728 KB Output is correct
9 Correct 1440 ms 101604 KB Output is correct
10 Correct 773 ms 101400 KB Output is correct
11 Correct 1531 ms 146020 KB Output is correct
12 Correct 2102 ms 145764 KB Output is correct
13 Correct 1850 ms 101384 KB Output is correct
14 Correct 1785 ms 101376 KB Output is correct
15 Correct 1625 ms 101308 KB Output is correct
16 Correct 1697 ms 141028 KB Output is correct
17 Correct 1020 ms 101444 KB Output is correct
18 Correct 1344 ms 140772 KB Output is correct
19 Correct 1762 ms 101280 KB Output is correct
20 Correct 1801 ms 101312 KB Output is correct
21 Correct 1893 ms 101236 KB Output is correct
22 Correct 772 ms 101032 KB Output is correct
23 Correct 1552 ms 145516 KB Output is correct
24 Correct 2064 ms 145096 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 28536 KB Output is correct
2 Correct 39 ms 28536 KB Output is correct
3 Correct 40 ms 28652 KB Output is correct
4 Runtime error 83 ms 57592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -