oj.uz

Submission #521471

# Submission time Handle Problem Language Result Execution time Memory
521471 2022-02-02T08:16:15 Z errorgorn Osumnjičeni (COCI21_osumnjiceni) C++17
60 / 110
 1000 ms 84096 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define ub upper_bound
#define lb lower_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));(s)<(e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(177013);

struct node{
	int s,e,m;
	int val=0,lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=max(l->val,r->val);
		}
	}
	
	int query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,400005);

int n,q;
ii arr[200005];

int nxt[200005];
int tkd[200005][20];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	
	vector<int> uni;
	rep(x,1,n+1) uni.pub(arr[x].fi),uni.pub(arr[x].se);
	sort(all(uni));
	unordered_map<int,int> id;
	rep(x,0,sz(uni)) id[uni[x]]=x;
	rep(x,1,n+1) arr[x].fi=id[arr[x].fi],arr[x].se=id[arr[x].se];
	
	int curr=n;
	rep(x,n+1,1){
		while (root->query(arr[x].fi,arr[x].se)){
			root->update(arr[curr].fi,arr[curr].se,-1);
			curr--;
		}
		root->update(arr[x].fi,arr[x].se,1);
		
		nxt[x]=curr+1;
	}
	
	memset(tkd,-1,sizeof(tkd));
	rep(x,1,n+1) tkd[x][0]=nxt[x];
	
	rep(y,0,18) rep(x,1,n+1) if (tkd[x][y]!=-1){
		tkd[x][y+1]=tkd[tkd[x][y]][y];
	}
	
	cin>>q;
	
	int a,b;
	while (q--){
		cin>>a>>b;
		
		int ans=0;
		rep(x,19,0) if (tkd[a][x]!=-1 && tkd[a][x]<=b){
			ans+=(1<<x);
			a=tkd[a][x];
		}
		
		cout<<ans+1<<endl;
	}
}

Compilation message

Main.cpp: In constructor 'node::node(int, int)':
Main.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 79924 KB Output is correct
2 Correct 842 ms 79696 KB Output is correct
3 Correct 784 ms 79752 KB Output is correct
4 Correct 769 ms 79976 KB Output is correct
5 Correct 780 ms 81000 KB Output is correct
6 Correct 158 ms 62136 KB Output is correct
7 Correct 163 ms 62312 KB Output is correct
8 Correct 188 ms 62260 KB Output is correct
9 Correct 207 ms 62544 KB Output is correct
10 Correct 207 ms 62208 KB Output is correct
11 Correct 381 ms 79944 KB Output is correct
12 Correct 375 ms 78692 KB Output is correct
13 Correct 373 ms 78580 KB Output is correct
14 Correct 506 ms 79944 KB Output is correct
15 Correct 512 ms 79352 KB Output is correct
16 Correct 39 ms 53544 KB Output is correct
17 Correct 168 ms 62680 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 54148 KB Output is correct
2 Correct 47 ms 54140 KB Output is correct
3 Correct 53 ms 54188 KB Output is correct
4 Correct 60 ms 54124 KB Output is correct
5 Correct 50 ms 54128 KB Output is correct
6 Correct 43 ms 53884 KB Output is correct
7 Correct 53 ms 54096 KB Output is correct
8 Correct 42 ms 53876 KB Output is correct
9 Correct 45 ms 53892 KB Output is correct
10 Correct 56 ms 53824 KB Output is correct
11 Correct 44 ms 54092 KB Output is correct
12 Correct 42 ms 54156 KB Output is correct
13 Correct 47 ms 54104 KB Output is correct
14 Correct 46 ms 54176 KB Output is correct
15 Correct 45 ms 54144 KB Output is correct
16 Correct 49 ms 53448 KB Output is correct
17 Correct 44 ms 53868 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 54148 KB Output is correct
2 Correct 47 ms 54140 KB Output is correct
3 Correct 53 ms 54188 KB Output is correct
4 Correct 60 ms 54124 KB Output is correct
5 Correct 50 ms 54128 KB Output is correct
6 Correct 43 ms 53884 KB Output is correct
7 Correct 53 ms 54096 KB Output is correct
8 Correct 42 ms 53876 KB Output is correct
9 Correct 45 ms 53892 KB Output is correct
10 Correct 56 ms 53824 KB Output is correct
11 Correct 44 ms 54092 KB Output is correct
12 Correct 42 ms 54156 KB Output is correct
13 Correct 47 ms 54104 KB Output is correct
14 Correct 46 ms 54176 KB Output is correct
15 Correct 45 ms 54144 KB Output is correct
16 Correct 49 ms 53448 KB Output is correct
17 Correct 44 ms 53868 KB Output is correct
18 Correct 114 ms 56900 KB Output is correct
19 Correct 107 ms 56556 KB Output is correct
20 Correct 114 ms 56892 KB Output is correct
21 Correct 118 ms 56616 KB Output is correct
22 Correct 115 ms 56768 KB Output is correct
23 Correct 113 ms 56308 KB Output is correct
24 Correct 104 ms 56416 KB Output is correct
25 Correct 107 ms 56468 KB Output is correct
26 Correct 104 ms 56416 KB Output is correct
27 Correct 101 ms 56168 KB Output is correct
28 Correct 89 ms 56268 KB Output is correct
29 Correct 84 ms 56212 KB Output is correct
30 Correct 96 ms 56280 KB Output is correct
31 Correct 94 ms 56176 KB Output is correct
32 Correct 86 ms 56260 KB Output is correct
33 Correct 38 ms 53440 KB Output is correct
34 Correct 94 ms 56164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 80932 KB Output is correct
2 Correct 801 ms 80492 KB Output is correct
3 Correct 748 ms 78976 KB Output is correct
4 Correct 769 ms 78764 KB Output is correct
5 Correct 760 ms 79412 KB Output is correct
6 Correct 165 ms 62172 KB Output is correct
7 Correct 164 ms 62156 KB Output is correct
8 Correct 175 ms 62108 KB Output is correct
9 Correct 183 ms 62108 KB Output is correct
10 Correct 197 ms 62692 KB Output is correct
11 Correct 394 ms 78376 KB Output is correct
12 Correct 392 ms 80456 KB Output is correct
13 Correct 390 ms 78416 KB Output is correct
14 Correct 467 ms 79008 KB Output is correct
15 Correct 531 ms 80196 KB Output is correct
16 Correct 42 ms 53444 KB Output is correct
17 Correct 165 ms 62308 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 79924 KB Output is correct
2 Correct 842 ms 79696 KB Output is correct
3 Correct 784 ms 79752 KB Output is correct
4 Correct 769 ms 79976 KB Output is correct
5 Correct 780 ms 81000 KB Output is correct
6 Correct 158 ms 62136 KB Output is correct
7 Correct 163 ms 62312 KB Output is correct
8 Correct 188 ms 62260 KB Output is correct
9 Correct 207 ms 62544 KB Output is correct
10 Correct 207 ms 62208 KB Output is correct
11 Correct 381 ms 79944 KB Output is correct
12 Correct 375 ms 78692 KB Output is correct
13 Correct 373 ms 78580 KB Output is correct
14 Correct 506 ms 79944 KB Output is correct
15 Correct 512 ms 79352 KB Output is correct
16 Correct 39 ms 53544 KB Output is correct
17 Correct 168 ms 62680 KB Output is correct
18 Correct 58 ms 54148 KB Output is correct
19 Correct 47 ms 54140 KB Output is correct
20 Correct 53 ms 54188 KB Output is correct
21 Correct 60 ms 54124 KB Output is correct
22 Correct 50 ms 54128 KB Output is correct
23 Correct 43 ms 53884 KB Output is correct
24 Correct 53 ms 54096 KB Output is correct
25 Correct 42 ms 53876 KB Output is correct
26 Correct 45 ms 53892 KB Output is correct
27 Correct 56 ms 53824 KB Output is correct
28 Correct 44 ms 54092 KB Output is correct
29 Correct 42 ms 54156 KB Output is correct
30 Correct 47 ms 54104 KB Output is correct
31 Correct 46 ms 54176 KB Output is correct
32 Correct 45 ms 54144 KB Output is correct
33 Correct 49 ms 53448 KB Output is correct
34 Correct 44 ms 53868 KB Output is correct
35 Correct 114 ms 56900 KB Output is correct
36 Correct 107 ms 56556 KB Output is correct
37 Correct 114 ms 56892 KB Output is correct
38 Correct 118 ms 56616 KB Output is correct
39 Correct 115 ms 56768 KB Output is correct
40 Correct 113 ms 56308 KB Output is correct
41 Correct 104 ms 56416 KB Output is correct
42 Correct 107 ms 56468 KB Output is correct
43 Correct 104 ms 56416 KB Output is correct
44 Correct 101 ms 56168 KB Output is correct
45 Correct 89 ms 56268 KB Output is correct
46 Correct 84 ms 56212 KB Output is correct
47 Correct 96 ms 56280 KB Output is correct
48 Correct 94 ms 56176 KB Output is correct
49 Correct 86 ms 56260 KB Output is correct
50 Correct 38 ms 53440 KB Output is correct
51 Correct 94 ms 56164 KB Output is correct
52 Correct 842 ms 80932 KB Output is correct
53 Correct 801 ms 80492 KB Output is correct
54 Correct 748 ms 78976 KB Output is correct
55 Correct 769 ms 78764 KB Output is correct
56 Correct 760 ms 79412 KB Output is correct
57 Correct 165 ms 62172 KB Output is correct
58 Correct 164 ms 62156 KB Output is correct
59 Correct 175 ms 62108 KB Output is correct
60 Correct 183 ms 62108 KB Output is correct
61 Correct 197 ms 62692 KB Output is correct
62 Correct 394 ms 78376 KB Output is correct
63 Correct 392 ms 80456 KB Output is correct
64 Correct 390 ms 78416 KB Output is correct
65 Correct 467 ms 79008 KB Output is correct
66 Correct 531 ms 80196 KB Output is correct
67 Correct 42 ms 53444 KB Output is correct
68 Correct 165 ms 62308 KB Output is correct
69 Correct 938 ms 82876 KB Output is correct
70 Execution timed out 1035 ms 84096 KB Time limit exceeded
71 Halted 0 ms 0 KB -