oj.uz

Submission #896435

# Submission time Handle Problem Language Result Execution time Memory
896435 2024-01-01T12:40:20 Z pan Osumnjičeni (COCI21_osumnjiceni) C++17
110 / 110
 859 ms 67404 KB 
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef int ll;
typedef pair<ll, ll> pi;


struct node{
    int s, e, m; //range is [s,e], m is the middle point
    ll val; //sum of [s,e]
    ll lazy; //lazy tag of [s,e]
    node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e]
    node (int S, int E){ //constructor called node
       s = S, e = E, m = (s+e)/2;
       val = 0; //initially all values are 0
       lazy = 0; //lazy tag of 0 will mean there is no update (sentinel value)
       l=r=nullptr;

	}
	void create()
	{
		if(s != e && l==nullptr){ //node is not yet a leaf, so create two children
		     l = new node(s, m); //create left child
             r = new node(m+1, e); //create right child
		 }
	}
 
    void propogate(){
       if (lazy==0) return; //nothing happens
       create();
       val+=lazy; //(e-s+1) is the length of the range
       if (s != e){ //not a leaf, send lazy tags to children
           l->lazy+=lazy;
           r->lazy+=lazy;
       }
       lazy=0; //set our lazy tag value back to the sentinel
    }
    void update(int S, int E, ll V){ //increment [S,E] by V
	   propogate();
       if(s==S && e==E) lazy += V; //update covers range, update lazy tag
       else{ //go we have to go deeper
		   create();
           if(E <= m) l->update(S, E, V); //[S,E] is in the left child
           else if (m < S) r->update(S, E, V); //[S,E] is in the right child
           else l->update(S, m, V),r->update(m+1, E, V);
           l->propogate(),r->propogate();
           //remember to propogate your children before update yourself
           val = max(l->val, r->val); //update the range sum
       }
    }
    ll query(int S, int E){
       propogate(); //remember to propogate
       if(s == S && e == E) return val; //case 1
       create();
       if(E <= m) return l->query(S, E); //case 2, recurse to left child
       else if(S >= m+1) return r->query(S, E); //case 3, recurse to right child
       else return max(l->query(S, m), r->query(m+1, E)); //case 4, split the query range, recurse to both childs
}
} *root;


ll n, q, l, r;
pi suspect[200005];
vector<ll> dis;

ll twok[200005][25];

ll solve2k(ll l, ll r)
{
	ll counter = 1;
	for (ll k=18; k>=0; k--)
	{
		if (twok[l][k]<=r)
		{
			counter+= (1LL<<k);
			l=twok[l][k];
		}
	}
	return counter;
	
}
int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> n;
	dis.resize(2*n+1);
	for (ll i=1; i<=n; ++i)
	{
		cin >> l >> r;
		suspect[i] = mp(l,r);
		dis[2*i]= r, dis[2*i-1] = l;
	}
	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());
	for (ll i=1; i<=n; ++i)
	{
		suspect[i].f = lb(dis.begin(), dis.end(), suspect[i].f)-dis.begin();
		suspect[i].s = lb(dis.begin(), dis.end(), suspect[i].s)-dis.begin();
	}
	ll r= 0;
	root = new node(0, dis.size()+5);
	for (ll i=1; i<=n; ++i)
	{
		for (ll j=1; j<19; ++j)
		{
			twok[i][j] = n+1;
		}
	}
	for (ll l=1; l<=n; ++l)
	{
		if (l!=1)
		{
			root->update(suspect[l-1].f, suspect[l-1].s, -1);
		}
		while (r+1<=n)
		{
			if (root->query(suspect[r+1].f, suspect[r+1].s)==0) 
			{
				r++;
				root->update(suspect[r].f, suspect[r].s, 1);
			}
			else 
			{
				break;
			}
		}
		twok[l][0] = r+1;
	}
	for (ll k=1; k<19; k++)
	{
		for (ll x=1; x<=n; ++x)
		{
			if (twok[x][k-1]==n+1) continue;
			twok[x][k] = twok[twok[x][k-1]][k-1];
		}
	}
	cin >> q;
	while (q--)
	{
		cin >> l >> r;
		cout << solve2k(l, r) << endl;
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 62548 KB Output is correct
2 Correct 545 ms 61992 KB Output is correct
3 Correct 538 ms 62036 KB Output is correct
4 Correct 530 ms 62592 KB Output is correct
5 Correct 550 ms 64220 KB Output is correct
6 Correct 61 ms 26332 KB Output is correct
7 Correct 72 ms 26704 KB Output is correct
8 Correct 71 ms 26452 KB Output is correct
9 Correct 75 ms 26452 KB Output is correct
10 Correct 82 ms 26480 KB Output is correct
11 Correct 358 ms 63032 KB Output is correct
12 Correct 303 ms 60276 KB Output is correct
13 Correct 323 ms 60392 KB Output is correct
14 Correct 358 ms 62996 KB Output is correct
15 Correct 358 ms 62228 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 72 ms 26804 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5720 KB Output is correct
2 Correct 14 ms 5468 KB Output is correct
3 Correct 14 ms 5464 KB Output is correct
4 Correct 17 ms 5468 KB Output is correct
5 Correct 14 ms 5468 KB Output is correct
6 Correct 8 ms 4700 KB Output is correct
7 Correct 9 ms 4792 KB Output is correct
8 Correct 8 ms 4952 KB Output is correct
9 Correct 9 ms 4696 KB Output is correct
10 Correct 8 ms 4700 KB Output is correct
11 Correct 11 ms 5468 KB Output is correct
12 Correct 11 ms 5468 KB Output is correct
13 Correct 11 ms 5468 KB Output is correct
14 Correct 11 ms 5468 KB Output is correct
15 Correct 11 ms 5468 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 11 ms 4604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5720 KB Output is correct
2 Correct 14 ms 5468 KB Output is correct
3 Correct 14 ms 5464 KB Output is correct
4 Correct 17 ms 5468 KB Output is correct
5 Correct 14 ms 5468 KB Output is correct
6 Correct 8 ms 4700 KB Output is correct
7 Correct 9 ms 4792 KB Output is correct
8 Correct 8 ms 4952 KB Output is correct
9 Correct 9 ms 4696 KB Output is correct
10 Correct 8 ms 4700 KB Output is correct
11 Correct 11 ms 5468 KB Output is correct
12 Correct 11 ms 5468 KB Output is correct
13 Correct 11 ms 5468 KB Output is correct
14 Correct 11 ms 5468 KB Output is correct
15 Correct 11 ms 5468 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 11 ms 4604 KB Output is correct
18 Correct 282 ms 6508 KB Output is correct
19 Correct 245 ms 6228 KB Output is correct
20 Correct 277 ms 6960 KB Output is correct
21 Correct 247 ms 6288 KB Output is correct
22 Correct 262 ms 6224 KB Output is correct
23 Correct 239 ms 5764 KB Output is correct
24 Correct 319 ms 5368 KB Output is correct
25 Correct 266 ms 5576 KB Output is correct
26 Correct 251 ms 5544 KB Output is correct
27 Correct 244 ms 5328 KB Output is correct
28 Correct 232 ms 5884 KB Output is correct
29 Correct 244 ms 5972 KB Output is correct
30 Correct 255 ms 6316 KB Output is correct
31 Correct 238 ms 5972 KB Output is correct
32 Correct 235 ms 6040 KB Output is correct
33 Correct 0 ms 2392 KB Output is correct
34 Correct 249 ms 5692 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 64492 KB Output is correct
2 Correct 555 ms 63568 KB Output is correct
3 Correct 486 ms 60604 KB Output is correct
4 Correct 507 ms 60224 KB Output is correct
5 Correct 519 ms 61572 KB Output is correct
6 Correct 60 ms 26448 KB Output is correct
7 Correct 68 ms 26192 KB Output is correct
8 Correct 75 ms 26192 KB Output is correct
9 Correct 71 ms 26184 KB Output is correct
10 Correct 106 ms 26560 KB Output is correct
11 Correct 319 ms 59988 KB Output is correct
12 Correct 338 ms 63964 KB Output is correct
13 Correct 317 ms 60004 KB Output is correct
14 Correct 363 ms 61408 KB Output is correct
15 Correct 359 ms 63576 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 64 ms 26452 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 62548 KB Output is correct
2 Correct 545 ms 61992 KB Output is correct
3 Correct 538 ms 62036 KB Output is correct
4 Correct 530 ms 62592 KB Output is correct
5 Correct 550 ms 64220 KB Output is correct
6 Correct 61 ms 26332 KB Output is correct
7 Correct 72 ms 26704 KB Output is correct
8 Correct 71 ms 26452 KB Output is correct
9 Correct 75 ms 26452 KB Output is correct
10 Correct 82 ms 26480 KB Output is correct
11 Correct 358 ms 63032 KB Output is correct
12 Correct 303 ms 60276 KB Output is correct
13 Correct 323 ms 60392 KB Output is correct
14 Correct 358 ms 62996 KB Output is correct
15 Correct 358 ms 62228 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 72 ms 26804 KB Output is correct
18 Correct 15 ms 5720 KB Output is correct
19 Correct 14 ms 5468 KB Output is correct
20 Correct 14 ms 5464 KB Output is correct
21 Correct 17 ms 5468 KB Output is correct
22 Correct 14 ms 5468 KB Output is correct
23 Correct 8 ms 4700 KB Output is correct
24 Correct 9 ms 4792 KB Output is correct
25 Correct 8 ms 4952 KB Output is correct
26 Correct 9 ms 4696 KB Output is correct
27 Correct 8 ms 4700 KB Output is correct
28 Correct 11 ms 5468 KB Output is correct
29 Correct 11 ms 5468 KB Output is correct
30 Correct 11 ms 5468 KB Output is correct
31 Correct 11 ms 5468 KB Output is correct
32 Correct 11 ms 5468 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 11 ms 4604 KB Output is correct
35 Correct 282 ms 6508 KB Output is correct
36 Correct 245 ms 6228 KB Output is correct
37 Correct 277 ms 6960 KB Output is correct
38 Correct 247 ms 6288 KB Output is correct
39 Correct 262 ms 6224 KB Output is correct
40 Correct 239 ms 5764 KB Output is correct
41 Correct 319 ms 5368 KB Output is correct
42 Correct 266 ms 5576 KB Output is correct
43 Correct 251 ms 5544 KB Output is correct
44 Correct 244 ms 5328 KB Output is correct
45 Correct 232 ms 5884 KB Output is correct
46 Correct 244 ms 5972 KB Output is correct
47 Correct 255 ms 6316 KB Output is correct
48 Correct 238 ms 5972 KB Output is correct
49 Correct 235 ms 6040 KB Output is correct
50 Correct 0 ms 2392 KB Output is correct
51 Correct 249 ms 5692 KB Output is correct
52 Correct 622 ms 64492 KB Output is correct
53 Correct 555 ms 63568 KB Output is correct
54 Correct 486 ms 60604 KB Output is correct
55 Correct 507 ms 60224 KB Output is correct
56 Correct 519 ms 61572 KB Output is correct
57 Correct 60 ms 26448 KB Output is correct
58 Correct 68 ms 26192 KB Output is correct
59 Correct 75 ms 26192 KB Output is correct
60 Correct 71 ms 26184 KB Output is correct
61 Correct 106 ms 26560 KB Output is correct
62 Correct 319 ms 59988 KB Output is correct
63 Correct 338 ms 63964 KB Output is correct
64 Correct 317 ms 60004 KB Output is correct
65 Correct 363 ms 61408 KB Output is correct
66 Correct 359 ms 63576 KB Output is correct
67 Correct 0 ms 2392 KB Output is correct
68 Correct 64 ms 26452 KB Output is correct
69 Correct 830 ms 65104 KB Output is correct
70 Correct 837 ms 67404 KB Output is correct
71 Correct 828 ms 63604 KB Output is correct
72 Correct 859 ms 66224 KB Output is correct
73 Correct 859 ms 65388 KB Output is correct
74 Correct 421 ms 30544 KB Output is correct
75 Correct 403 ms 29792 KB Output is correct
76 Correct 419 ms 30804 KB Output is correct
77 Correct 374 ms 29924 KB Output is correct
78 Correct 399 ms 30036 KB Output is correct
79 Correct 655 ms 66568 KB Output is correct
80 Correct 557 ms 62912 KB Output is correct
81 Correct 576 ms 63108 KB Output is correct
82 Correct 659 ms 65432 KB Output is correct
83 Correct 553 ms 62984 KB Output is correct
84 Correct 1 ms 2396 KB Output is correct
85 Correct 326 ms 30032 KB Output is correct