oj.uz

Submission #896410

# Submission time Handle Problem Language Result Execution time Memory
896410 2024-01-01T11:59:36 Z pan Osumnjičeni (COCI21_osumnjiceni) C++17
30 / 110
 1000 ms 524288 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 long long int ll;
typedef pair<ll, ll> pi;


struct node{
    ll 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 (ll S, ll 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(ll S, ll 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(ll S, ll 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, minl = LLONG_MAX, maxr = 0;
vector<pi> suspect;

ll twok[200005][25];

ll solve2k(ll l, ll r)
{
	ll counter = 1;
	for (ll k=19; k>=0; k--)
	{
		if (twok[l][k]<=r)
		{
			counter+= (1<<k);
			l=twok[l][k];
		}
	}
	return counter;
	
}
int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> n;
	suspect.resize(n+1);
	for (ll i=1; i<=n; ++i)
	{
		cin >> l >> r;
		minl = min(minl, l);
		maxr= max(r, maxr);
		suspect[i] = mp(l,r);
	}
	ll r= 0;
	root = new node(max(0LL, minl-5), maxr+5);
	for (ll i=0; i<=n; ++i)
	{
		for (ll j=0; j<=20; ++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)
		{
			root->update(suspect[r+1].f, suspect[r+1].s, 1);
			if (root->query(minl, maxr)<=1) {r++;}
			else 
			{
				root->update(suspect[r+1].f, suspect[r+1].s, -1);
				break;
			}
		}
		twok[l][0] = r+1;
	}
	for (ll k=1; k<20; 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 32080 KB Output is correct
2 Correct 44 ms 30432 KB Output is correct
3 Correct 44 ms 30544 KB Output is correct
4 Correct 46 ms 31692 KB Output is correct
5 Correct 44 ms 30212 KB Output is correct
6 Correct 8 ms 2904 KB Output is correct
7 Correct 15 ms 2900 KB Output is correct
8 Correct 13 ms 2908 KB Output is correct
9 Correct 13 ms 2916 KB Output is correct
10 Correct 13 ms 3192 KB Output is correct
11 Correct 17 ms 12020 KB Output is correct
12 Correct 16 ms 11352 KB Output is correct
13 Correct 17 ms 11656 KB Output is correct
14 Correct 22 ms 11816 KB Output is correct
15 Correct 24 ms 12048 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 2896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 32080 KB Output is correct
2 Correct 44 ms 30432 KB Output is correct
3 Correct 44 ms 30544 KB Output is correct
4 Correct 46 ms 31692 KB Output is correct
5 Correct 44 ms 30212 KB Output is correct
6 Correct 8 ms 2904 KB Output is correct
7 Correct 15 ms 2900 KB Output is correct
8 Correct 13 ms 2908 KB Output is correct
9 Correct 13 ms 2916 KB Output is correct
10 Correct 13 ms 3192 KB Output is correct
11 Correct 17 ms 12020 KB Output is correct
12 Correct 16 ms 11352 KB Output is correct
13 Correct 17 ms 11656 KB Output is correct
14 Correct 22 ms 11816 KB Output is correct
15 Correct 24 ms 12048 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 2896 KB Output is correct
18 Correct 304 ms 34276 KB Output is correct
19 Correct 283 ms 33108 KB Output is correct
20 Correct 305 ms 34900 KB Output is correct
21 Correct 287 ms 33012 KB Output is correct
22 Correct 290 ms 32456 KB Output is correct
23 Correct 243 ms 5156 KB Output is correct
24 Correct 287 ms 5444 KB Output is correct
25 Correct 268 ms 5456 KB Output is correct
26 Correct 263 ms 5532 KB Output is correct
27 Correct 246 ms 5204 KB Output is correct
28 Correct 254 ms 13800 KB Output is correct
29 Correct 251 ms 13396 KB Output is correct
30 Correct 249 ms 13572 KB Output is correct
31 Correct 260 ms 13312 KB Output is correct
32 Correct 258 ms 14160 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 262 ms 5056 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 939 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -