oj.uz

Submission #678371

# Submission time Handle Problem Language Result Execution time Memory
678371 2023-01-05T16:54:31 Z Just_ Examination (JOI19_examination) C++17
100 / 100
 1161 ms 58832 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<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const long long INF=1e18,mod=998244353;
int n,q;
const int N=1e5+5;
int s[N],t[N],x[N],y[N],z[N],ans[N];
struct BIT{
	ordered_set T[N];
	void update(int i, int v){
		i=N-i-1;
		for(;i<N;i+=(i&-i))
			T[i].insert(v);
	}
	int query(int i, int v){
		int res=0;i=N-i-1;
		for(;i>0;i-=(i&-i))
			res+=((int)T[i].size()-T[i].order_of_key(v));
		return res;
	}
} T;
bool c1(int a, int b){
	return x[a]>x[b];
}
bool c2(int a, int b){
	return s[a]>s[b];
}
vector<int> a,b;
void add(int i){
	int x=lower_bound(all(a),t[i])-a.begin();
	int y=lower_bound(all(b),s[i]+t[i])-b.begin();
	T.update(x,y);
}
void solve(){
	cin>>n>>q;
	vector<int> pa(n);
	for(int i=0;i<n;i++){
		cin>>s[i]>>t[i];
		pa[i]=i;
		a.pb(t[i]);
		b.pb(s[i]+t[i]);
	}
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	sort(all(b));
	b.erase(unique(all(b)),b.end());
	vector<int> pb(q);
	for(int i=0;i<q;i++){
		cin>>x[i]>>y[i]>>z[i];
		pb[i]=i;
	}
	sort(all(pa),c2);
	sort(all(pb),c1);
	int r=0;
	for(auto it: pb){
		while(r<n && s[pa[r]]>=x[it])
			add(pa[r++]);
		int k=lower_bound(all(a),y[it])-a.begin();
		int j=lower_bound(all(b),z[it])-b.begin();
		ans[it]=T.query(k,j);
	}
	for(int i=0;i<q;i++)
		cout<<ans[i]<<'\n';
}
main(){
	//fopn("newbarn");
	//ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message

examination.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main(){
      | ^~~~
examination.cpp: In function 'void fopn(std::string)':
examination.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8148 KB Output is correct
2 Correct 7 ms 8136 KB Output is correct
3 Correct 7 ms 8144 KB Output is correct
4 Correct 7 ms 8140 KB Output is correct
5 Correct 7 ms 8136 KB Output is correct
6 Correct 7 ms 8148 KB Output is correct
7 Correct 18 ms 9172 KB Output is correct
8 Correct 19 ms 9168 KB Output is correct
9 Correct 18 ms 9172 KB Output is correct
10 Correct 16 ms 8704 KB Output is correct
11 Correct 17 ms 9176 KB Output is correct
12 Correct 11 ms 8528 KB Output is correct
13 Correct 16 ms 9204 KB Output is correct
14 Correct 16 ms 9124 KB Output is correct
15 Correct 17 ms 9168 KB Output is correct
16 Correct 15 ms 9172 KB Output is correct
17 Correct 13 ms 8540 KB Output is correct
18 Correct 11 ms 8404 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 54036 KB Output is correct
2 Correct 889 ms 54144 KB Output is correct
3 Correct 881 ms 54112 KB Output is correct
4 Correct 281 ms 24508 KB Output is correct
5 Correct 649 ms 53420 KB Output is correct
6 Correct 210 ms 23796 KB Output is correct
7 Correct 976 ms 54076 KB Output is correct
8 Correct 800 ms 54140 KB Output is correct
9 Correct 802 ms 54012 KB Output is correct
10 Correct 601 ms 53292 KB Output is correct
11 Correct 182 ms 18840 KB Output is correct
12 Correct 136 ms 17920 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 54036 KB Output is correct
2 Correct 889 ms 54144 KB Output is correct
3 Correct 881 ms 54112 KB Output is correct
4 Correct 281 ms 24508 KB Output is correct
5 Correct 649 ms 53420 KB Output is correct
6 Correct 210 ms 23796 KB Output is correct
7 Correct 976 ms 54076 KB Output is correct
8 Correct 800 ms 54140 KB Output is correct
9 Correct 802 ms 54012 KB Output is correct
10 Correct 601 ms 53292 KB Output is correct
11 Correct 182 ms 18840 KB Output is correct
12 Correct 136 ms 17920 KB Output is correct
13 Correct 954 ms 54524 KB Output is correct
14 Correct 914 ms 54644 KB Output is correct
15 Correct 864 ms 54096 KB Output is correct
16 Correct 304 ms 24940 KB Output is correct
17 Correct 687 ms 53716 KB Output is correct
18 Correct 198 ms 23876 KB Output is correct
19 Correct 1010 ms 54496 KB Output is correct
20 Correct 977 ms 54596 KB Output is correct
21 Correct 1065 ms 54552 KB Output is correct
22 Correct 582 ms 53364 KB Output is correct
23 Correct 218 ms 18752 KB Output is correct
24 Correct 138 ms 17892 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8148 KB Output is correct
2 Correct 7 ms 8136 KB Output is correct
3 Correct 7 ms 8144 KB Output is correct
4 Correct 7 ms 8140 KB Output is correct
5 Correct 7 ms 8136 KB Output is correct
6 Correct 7 ms 8148 KB Output is correct
7 Correct 18 ms 9172 KB Output is correct
8 Correct 19 ms 9168 KB Output is correct
9 Correct 18 ms 9172 KB Output is correct
10 Correct 16 ms 8704 KB Output is correct
11 Correct 17 ms 9176 KB Output is correct
12 Correct 11 ms 8528 KB Output is correct
13 Correct 16 ms 9204 KB Output is correct
14 Correct 16 ms 9124 KB Output is correct
15 Correct 17 ms 9168 KB Output is correct
16 Correct 15 ms 9172 KB Output is correct
17 Correct 13 ms 8540 KB Output is correct
18 Correct 11 ms 8404 KB Output is correct
19 Correct 870 ms 54036 KB Output is correct
20 Correct 889 ms 54144 KB Output is correct
21 Correct 881 ms 54112 KB Output is correct
22 Correct 281 ms 24508 KB Output is correct
23 Correct 649 ms 53420 KB Output is correct
24 Correct 210 ms 23796 KB Output is correct
25 Correct 976 ms 54076 KB Output is correct
26 Correct 800 ms 54140 KB Output is correct
27 Correct 802 ms 54012 KB Output is correct
28 Correct 601 ms 53292 KB Output is correct
29 Correct 182 ms 18840 KB Output is correct
30 Correct 136 ms 17920 KB Output is correct
31 Correct 954 ms 54524 KB Output is correct
32 Correct 914 ms 54644 KB Output is correct
33 Correct 864 ms 54096 KB Output is correct
34 Correct 304 ms 24940 KB Output is correct
35 Correct 687 ms 53716 KB Output is correct
36 Correct 198 ms 23876 KB Output is correct
37 Correct 1010 ms 54496 KB Output is correct
38 Correct 977 ms 54596 KB Output is correct
39 Correct 1065 ms 54552 KB Output is correct
40 Correct 582 ms 53364 KB Output is correct
41 Correct 218 ms 18752 KB Output is correct
42 Correct 138 ms 17892 KB Output is correct
43 Correct 1088 ms 58652 KB Output is correct
44 Correct 1044 ms 58720 KB Output is correct
45 Correct 997 ms 58832 KB Output is correct
46 Correct 341 ms 26060 KB Output is correct
47 Correct 750 ms 57052 KB Output is correct
48 Correct 214 ms 23704 KB Output is correct
49 Correct 1161 ms 58688 KB Output is correct
50 Correct 1042 ms 58544 KB Output is correct
51 Correct 1049 ms 58476 KB Output is correct
52 Correct 735 ms 56964 KB Output is correct
53 Correct 233 ms 19668 KB Output is correct