oj.uz

Submission #402905

# Submission time Handle Problem Language Result Execution time Memory
402905 2021-05-12T13:32:27 Z keta_tsimakuridze Examination (JOI19_examination) C++14
0 / 100
 2021 ms 197980 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
#define f first
#define s second
#define int long long
#define pii pair<int,int> 
using namespace __gnu_pbds; 
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,n,Q,ans[N];
pair<int,int>p[N];
vector<int> x;
pair<pair<int,int>,pair<int,int> >q[N];
map<int,int>ind;

 
typedef tree<pii, null_type, less<pii>, rb_tree_tag,  
            tree_order_statistics_node_update>  
    ordered_set;  
  ordered_set s[4*N];

void update(int u,int ind,int l,int r,int val,int idx){
	if(l>ind || r<ind) return;
	if(l==r) {
		s[u].insert({val,idx});
		return;
	}
	s[u].insert({val,idx});
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val,idx);
	update(2*u+1,ind,mid+1,r,val,idx);
}
int getans(int u,int start,int end,int l,int r,int val){
	if(l>end || r<start) return 0;
	if(start<=l&& r<=end) {
		return s[u].size() - s[u].order_of_key({val,0});
	}
	int mid=(l+r)/2;
	return getans(2*u,start,end,l,mid,val)+getans(2*u+1,start,end,mid+1,r,val);
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// t=1;
	cin>>n>>Q;
	for(int i=1;i<=n;i++){
		cin>>p[i].f>>p[i].s;
		x.push_back(p[i].s);
	}
	for(int i=1;i<=Q;i++){
		cin>>q[i].f.f>>q[i].f.s>>q[i].s.f;
		q[i].s.s=i;
		x.push_back(q[i].f.s);
	}
	sort(x.begin(),x.end());
	int idx=0;
	for(int i=0;i<x.size();i++){
		if(!i || x[i]!=x[i-1]) idx++;
		ind[x[i]] = idx;
	}
	sort(q+1,q+Q+1);
	sort(p+1,p+n+1);
	reverse(q+1,q+Q+1);
	reverse(p+1,p+n+1);
	int L=0;
	for(int i=1;i<=Q;i++){
		while(L<n && p[L+1].f>=q[i].f.f) L++,update(1,ind[p[L].s],1,idx,p[L].f+p[L].s,i);
		ans[q[i].s.s] = getans(1,ind[q[i].f.s],idx,1,idx,q[i].s.f);
	}
	for(int i=1;i<=Q;i++) cout<<ans[i]<<" ";
}

Compilation message

examination.cpp:43:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 |  main(){
      |  ^~~~
examination.cpp: In function 'int main()':
examination.cpp:58:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 75460 KB Output is correct
2 Correct 71 ms 75380 KB Output is correct
3 Correct 69 ms 75368 KB Output is correct
4 Correct 70 ms 75372 KB Output is correct
5 Correct 76 ms 75476 KB Output is correct
6 Correct 72 ms 75428 KB Output is correct
7 Correct 99 ms 78640 KB Output is correct
8 Correct 97 ms 78624 KB Output is correct
9 Correct 111 ms 78532 KB Output is correct
10 Correct 102 ms 76500 KB Output is correct
11 Correct 95 ms 78768 KB Output is correct
12 Incorrect 85 ms 75780 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2021 ms 197980 KB Output is correct
2 Incorrect 2008 ms 197936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2021 ms 197980 KB Output is correct
2 Incorrect 2008 ms 197936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 75460 KB Output is correct
2 Correct 71 ms 75380 KB Output is correct
3 Correct 69 ms 75368 KB Output is correct
4 Correct 70 ms 75372 KB Output is correct
5 Correct 76 ms 75476 KB Output is correct
6 Correct 72 ms 75428 KB Output is correct
7 Correct 99 ms 78640 KB Output is correct
8 Correct 97 ms 78624 KB Output is correct
9 Correct 111 ms 78532 KB Output is correct
10 Correct 102 ms 76500 KB Output is correct
11 Correct 95 ms 78768 KB Output is correct
12 Incorrect 85 ms 75780 KB Output isn't correct
13 Halted 0 ms 0 KB -