Submission #896435

#	Time	Username	Problem	Language	Result	Execution time	Memory
896435		pan	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	859 ms	67404 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 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50