oj.uz

Submission #126876

# Submission time Handle Problem Language Result Execution time Memory
126876 2019-07-08T14:41:20 Z MohamedAhmed04 Examination (JOI19_examination) C++14
20 / 100
 2674 ms 111272 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 = 100005;

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] ;

int main()
{
    int n , q ;
    scanf("%d %d" , &n, &q) ;
    for(int i = 0 ; i < n ; ++i)
    {
        cin>>a[i]>>b[i] ;
        a[i] += 2 ;
        b[i] += 2 ;
    }
    for(int i = 0 ; i < n ; ++i)
        update(a[i] , b[i] , i) ;
    while(q--)
    {
        int x , y , z ;
        cin>>x>>y>>z ;
        x += 2 ;
        y += 2 ;
        cout<<query(N-1 , N-1) - query(x-1 , N-1) - query(N-1 , y-1) + query(x-1 , y-1)<<"\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 Incorrect 14 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2524 ms 66032 KB Output is correct
2 Correct 2528 ms 66156 KB Output is correct
3 Correct 2470 ms 66100 KB Output is correct
4 Correct 2044 ms 66324 KB Output is correct
5 Correct 2416 ms 106360 KB Output is correct
6 Correct 1824 ms 106260 KB Output is correct
7 Correct 2067 ms 66168 KB Output is correct
8 Correct 2301 ms 66204 KB Output is correct
9 Correct 1852 ms 66184 KB Output is correct
10 Correct 1968 ms 111272 KB Output is correct
11 Correct 1686 ms 65940 KB Output is correct
12 Correct 2649 ms 111060 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2524 ms 66032 KB Output is correct
2 Correct 2528 ms 66156 KB Output is correct
3 Correct 2470 ms 66100 KB Output is correct
4 Correct 2044 ms 66324 KB Output is correct
5 Correct 2416 ms 106360 KB Output is correct
6 Correct 1824 ms 106260 KB Output is correct
7 Correct 2067 ms 66168 KB Output is correct
8 Correct 2301 ms 66204 KB Output is correct
9 Correct 1852 ms 66184 KB Output is correct
10 Correct 1968 ms 111272 KB Output is correct
11 Correct 1686 ms 65940 KB Output is correct
12 Correct 2649 ms 111060 KB Output is correct
13 Incorrect 2674 ms 66072 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -