Submission #1315413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315413		WH8	Index (COCI21_index)	C++17	110 / 110	676 ms	243364 KiB

index

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iiii tuple<int, int,int,int>
#define ld long double
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

struct Node {
       int v,s,e,m;
       Node *l, *r;
       Node (int S,int E){
              s=S, e=E, m=(s+e)/2, v=0;
              l=r=nullptr;
       }
} * roots[200005];
Node* dupe(Node *node){
       Node* ret=new Node(node->s,node->e);
       ret->v=node->v;
       ret->l=node->l; ret->r=node->r;
       return ret;
}
void update(Node * node, int S){ // pass pointer *
       int & s=node->s, & m=node->m, &e=node->e, &v=node->v;
       Node* &l=node->l;
       Node* &r= node->r;
       if(s==e){
		   v+=1;
           return;
       }
       if(S<=m){
              if(!l) l=new Node(s,m);
              else l=dupe(l);
              update(l, S);
       }
       else{
              if(!r) r=new Node(m+1,e);
              else r=dupe(r);
              update(r,S);
       }
       v=(l?l->v:0)+(r?r->v:0);
       //printf("SEGMENT %lld to %lld, v %lld, l %lld, r %lld\n",s,e,v, (l?l->v:0), (r?r->v:0));
}

int bs(int s, int e, int vr, Node * n1, Node * n2){// n1 - n2;
	if(!n1) {
		//printf("n1 doesnt exist %lld to %lld\n", s, e);
		if(vr < s)return -1;
		else return vr;
	}
	assert(s == n1->s and e == n1->e);
	int m=(s+e)/2;
	// if entire range doesnt work just return -1 immediately.
	int sum=n1->v - (n2?n2->v:0);
	//printf("value range %lld to %lld, sum %lld, vr %lld\n", s, e, sum, vr);
	if(sum + vr < s) {
		//printf("range cannot satisfy %lld to %lld\n", s, e);

		return -1;
	}
	if(s==e)return s; 
	int right=-1;
	right = bs(m+1, e, vr, n1->r, (n2?n2->r:nullptr));
	if(right != -1) return right;
	int sumonright=(n1->r ? n1->r->v : 0) - (n2?(n2->r? n2->r->v : 0):0);
	return bs(s, m, sumonright + vr, n1->l, (n2?n2->l:nullptr));
}

int ans[200005];
const int maxp=200005;

signed main() {
       int n, q;cin>>n>>q;
	   vector<int> ans(q), v(n+1);
	   vector<pll> qs(q);
       for(int i=1;i<=n;i++)cin>>v[i];
       for(int i=0;i<q;i++)cin>>qs[i].f>>qs[i].s;
       roots[0] = new Node(1, maxp);
       for(int i=1;i<=n;i++){
		   //printf("\nupdating i %lld\n", i);
              roots[i]=dupe(roots[i-1]);
              update(roots[i], v[i]);
       }
	   for(int i=0;i<q;i++){
		   auto [l, r] = qs[i];
		   //printf("\n answering %lld to %lld \n", l, r);
		   // binary search the difference of roots[r] and roots[l-1] 
		   ans[i]=bs(1, maxp, 0, roots[r], roots[l-1]);
	   }
       for(int i=0;i<q;i++){
              cout<<ans[i]<<"\n";
       }
       return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50