oj.uz

Submission #402899

# Submission time Handle Problem Language Result Execution time Memory
402899 2021-05-12T13:22:48 Z keta_tsimakuridze Examination (JOI19_examination) C++14
0 / 100
 2323 ms 193976 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int> 
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;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
using namespace __gnu_pbds;  
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){
	if(l>ind || r<ind) return;
	if(l==r) {
		s[u].insert({val,ind});
		return;
	}
	s[u].insert({val,ind});
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
}
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(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);
		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:40:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 |  main(){
      |  ^~~~
examination.cpp: In function 'int main()':
examination.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 75460 KB Output is correct
2 Correct 68 ms 75400 KB Output is correct
3 Correct 63 ms 75468 KB Output is correct
4 Correct 70 ms 75460 KB Output is correct
5 Correct 62 ms 75452 KB Output is correct
6 Correct 65 ms 75460 KB Output is correct
7 Correct 91 ms 78532 KB Output is correct
8 Correct 85 ms 78560 KB Output is correct
9 Correct 93 ms 78544 KB Output is correct
10 Incorrect 75 ms 76444 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2195 ms 193976 KB Output is correct
2 Correct 2323 ms 193972 KB Output is correct
3 Correct 2179 ms 193960 KB Output is correct
4 Incorrect 375 ms 104428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2195 ms 193976 KB Output is correct
2 Correct 2323 ms 193972 KB Output is correct
3 Correct 2179 ms 193960 KB Output is correct
4 Incorrect 375 ms 104428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 75460 KB Output is correct
2 Correct 68 ms 75400 KB Output is correct
3 Correct 63 ms 75468 KB Output is correct
4 Correct 70 ms 75460 KB Output is correct
5 Correct 62 ms 75452 KB Output is correct
6 Correct 65 ms 75460 KB Output is correct
7 Correct 91 ms 78532 KB Output is correct
8 Correct 85 ms 78560 KB Output is correct
9 Correct 93 ms 78544 KB Output is correct
10 Incorrect 75 ms 76444 KB Output isn't correct
11 Halted 0 ms 0 KB -