Submission #896410

#	Time	Username	Problem	Language	Result	Execution time	Memory
896410		pan	Osumnjičeni (COCI21_osumnjiceni)	C++17	30 / 110	1014 ms	524288 KiB

Main

#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
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50