oj.uz

Submission #957729

# Submission time Handle Problem Language Result Execution time Memory
957729 2024-04-04T08:56:16 Z 8pete8 Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 968 ms 321800 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include <cstdint>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mod=1e9+7,mxn=3e5+5,lg=30,inf=1e16,minf=-1e9,Mxn=1e6;
int n,q;
struct fen{
	int fwk[mxn+10];
	void update(int pos,int val){for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;}
	int qry(int pos){
		if(pos==0)return 0;
		int sum=0;
		for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
		return sum;
	}
}t;
pii nxt[mxn+10];
int pos[mxn+10],opos[mxn+10],rep[mxn+10];
//nx number that is more than cur,position of number in block
deque<int> com[mxn+10];
int split(int id,int x){
	int nxtid=com[id][x];
	t.update(id,-com[id].size()+x);
	t.update(nxtid,com[id].size()-x);
	if(2*x>com[id].size()){
		while(com[id].size()!=x){
			com[nxtid].push_front(com[id].back());
			com[id].pop_back();
		}
		
	}
	else{
		swap(com[id],com[nxtid]);
		for(int i=0;i<x;i++){
			com[id].push_back(com[nxtid].front());
			com[nxtid].pop_front();
		}
	}
	return nxtid;
}
void calblock(int x){
	int st=x;
	while(st!=inf&&(nxt[st].s-opos[st])<com[st].size()){
		split(st,nxt[st].s-opos[st]);
		st=nxt[st].f;
	}
}
/*
void print(){
	for(int i=1;i<=n;i++){
		for(auto j:com[i])cout<<j<<" ";
		//cout<<'\n';
	}
	cout<<'\n';
	for(int i=1;i<=n;i++)cout<<t.qry(i)-t.qry(i-1)<<" ";
	cout<<'\n';
}*/
int ans[Mxn+10];
pii get(int x){
	int l=1,r=n,pos=inf;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(t.qry(mid)>=x)r=mid-1,pos=min(pos,mid);
		else l=mid+1;
	}
	int y=(x)-(t.qry(pos)-com[pos].size());
	return {pos,y};
}
int32_t main(){
    fastio
	cin>>n>>q;
	vector<int>v(n);
	for(int i=0;i<n;i++)cin>>v[i],opos[v[i]]=i;
	for(int i=1;i<=n;i++)rep[i]=i;
	stack<pii>st;
	for(int i=n-1;i>=0;i--){
		while(!st.empty()&&v[i]>st.top().f)st.pop();
		nxt[v[i]]=((st.empty())?make_pair(inf,inf):st.top());
		st.push({v[i],i});
	}
	vector<pair<int,pii>>qry(q);
	for(int i=0;i<q;i++){
		cin>>qry[i].f>>qry[i].s.f,qry[i].s.s=i;
	}
	sort(all(qry));
	for(int i=0;i<n;i++)com[v[0]].pb(v[i]);
	t.update(v[0],n);
	calblock(v[0]);
	int cur=0;
	for(int i=0;i<n;i++){
		pii a;
		//print();
		while(cur<q&&qry[cur].f<=i){
			a=get(qry[cur].s.f);
			ans[qry[cur].s.s]=com[a.f][a.s-1];
			cur++;
		}
		a=get(n/2);
		if(com[a.f].size()<a.s)break;
		if(a.s==com[a.f].size())break;
		calblock(split(a.f,a.s));
	}
	while(cur<q){
		pii a=get(qry[cur].s.f);
		ans[qry[cur].s.s]=com[a.f][a.s-1];
		cur++;
	}
	for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
/*

*/






/*
10 0
7 5 2 9 10 8 4 3 6 1 
6 3
1 5 6 2 3 4
1 2 
0 4 

1 5
	*/

Compilation message

Main.cpp: In function 'long long int split(long long int, long long int)':
Main.cpp:57:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  if(2*x>com[id].size()){
      |     ~~~^~~~~~~~~~~~~~~
Main.cpp:58:23: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |   while(com[id].size()!=x){
      |         ~~~~~~~~~~~~~~^~~
Main.cpp: In function 'void calblock(long long int)':
Main.cpp:75:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  while(st!=inf&&(nxt[st].s-opos[st])<com[st].size()){
      |                 ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:131:21: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  131 |   if(com[a.f].size()<a.s)break;
      |                     ^
Main.cpp:132:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   if(a.s==com[a.f].size())break;
      |      ~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 245524 KB Output is correct
2 Correct 432 ms 252892 KB Output is correct
3 Correct 465 ms 251540 KB Output is correct
4 Correct 391 ms 250196 KB Output is correct
5 Correct 415 ms 252452 KB Output is correct
6 Correct 387 ms 250680 KB Output is correct
7 Correct 423 ms 252528 KB Output is correct
8 Correct 392 ms 250764 KB Output is correct
9 Correct 408 ms 250364 KB Output is correct
10 Correct 392 ms 250964 KB Output is correct
11 Correct 401 ms 250904 KB Output is correct
12 Correct 392 ms 249784 KB Output is correct
13 Correct 393 ms 250784 KB Output is correct
14 Correct 397 ms 251732 KB Output is correct
15 Correct 424 ms 251720 KB Output is correct
16 Correct 102 ms 211784 KB Output is correct
17 Correct 394 ms 250396 KB Output is correct
18 Correct 385 ms 249936 KB Output is correct
19 Correct 90 ms 211704 KB Output is correct
20 Correct 96 ms 211728 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 321800 KB Output is correct
2 Correct 499 ms 297556 KB Output is correct
3 Correct 420 ms 262736 KB Output is correct
4 Correct 490 ms 287032 KB Output is correct
5 Correct 492 ms 290612 KB Output is correct
6 Correct 481 ms 286832 KB Output is correct
7 Correct 467 ms 279368 KB Output is correct
8 Correct 512 ms 276684 KB Output is correct
9 Correct 459 ms 275028 KB Output is correct
10 Correct 476 ms 269380 KB Output is correct
11 Correct 427 ms 260692 KB Output is correct
12 Correct 435 ms 264104 KB Output is correct
13 Correct 468 ms 267500 KB Output is correct
14 Correct 414 ms 264048 KB Output is correct
15 Correct 484 ms 269528 KB Output is correct
16 Correct 118 ms 222548 KB Output is correct
17 Correct 460 ms 268356 KB Output is correct
18 Correct 435 ms 257940 KB Output is correct
19 Correct 195 ms 232020 KB Output is correct
20 Correct 194 ms 233812 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 247612 KB Output is correct
2 Correct 196 ms 235948 KB Output is correct
3 Correct 181 ms 223056 KB Output is correct
4 Correct 164 ms 227924 KB Output is correct
5 Correct 220 ms 245336 KB Output is correct
6 Correct 166 ms 229552 KB Output is correct
7 Correct 183 ms 238304 KB Output is correct
8 Correct 191 ms 230484 KB Output is correct
9 Correct 188 ms 237908 KB Output is correct
10 Correct 168 ms 222492 KB Output is correct
11 Correct 153 ms 222952 KB Output is correct
12 Correct 154 ms 222548 KB Output is correct
13 Correct 155 ms 223320 KB Output is correct
14 Correct 155 ms 223312 KB Output is correct
15 Correct 148 ms 220752 KB Output is correct
16 Correct 119 ms 217688 KB Output is correct
17 Correct 156 ms 224088 KB Output is correct
18 Correct 140 ms 220380 KB Output is correct
19 Correct 99 ms 211536 KB Output is correct
20 Correct 96 ms 211544 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 245524 KB Output is correct
2 Correct 432 ms 252892 KB Output is correct
3 Correct 465 ms 251540 KB Output is correct
4 Correct 391 ms 250196 KB Output is correct
5 Correct 415 ms 252452 KB Output is correct
6 Correct 387 ms 250680 KB Output is correct
7 Correct 423 ms 252528 KB Output is correct
8 Correct 392 ms 250764 KB Output is correct
9 Correct 408 ms 250364 KB Output is correct
10 Correct 392 ms 250964 KB Output is correct
11 Correct 401 ms 250904 KB Output is correct
12 Correct 392 ms 249784 KB Output is correct
13 Correct 393 ms 250784 KB Output is correct
14 Correct 397 ms 251732 KB Output is correct
15 Correct 424 ms 251720 KB Output is correct
16 Correct 102 ms 211784 KB Output is correct
17 Correct 394 ms 250396 KB Output is correct
18 Correct 385 ms 249936 KB Output is correct
19 Correct 90 ms 211704 KB Output is correct
20 Correct 96 ms 211728 KB Output is correct
21 Correct 535 ms 321800 KB Output is correct
22 Correct 499 ms 297556 KB Output is correct
23 Correct 420 ms 262736 KB Output is correct
24 Correct 490 ms 287032 KB Output is correct
25 Correct 492 ms 290612 KB Output is correct
26 Correct 481 ms 286832 KB Output is correct
27 Correct 467 ms 279368 KB Output is correct
28 Correct 512 ms 276684 KB Output is correct
29 Correct 459 ms 275028 KB Output is correct
30 Correct 476 ms 269380 KB Output is correct
31 Correct 427 ms 260692 KB Output is correct
32 Correct 435 ms 264104 KB Output is correct
33 Correct 468 ms 267500 KB Output is correct
34 Correct 414 ms 264048 KB Output is correct
35 Correct 484 ms 269528 KB Output is correct
36 Correct 118 ms 222548 KB Output is correct
37 Correct 460 ms 268356 KB Output is correct
38 Correct 435 ms 257940 KB Output is correct
39 Correct 195 ms 232020 KB Output is correct
40 Correct 194 ms 233812 KB Output is correct
41 Correct 259 ms 247612 KB Output is correct
42 Correct 196 ms 235948 KB Output is correct
43 Correct 181 ms 223056 KB Output is correct
44 Correct 164 ms 227924 KB Output is correct
45 Correct 220 ms 245336 KB Output is correct
46 Correct 166 ms 229552 KB Output is correct
47 Correct 183 ms 238304 KB Output is correct
48 Correct 191 ms 230484 KB Output is correct
49 Correct 188 ms 237908 KB Output is correct
50 Correct 168 ms 222492 KB Output is correct
51 Correct 153 ms 222952 KB Output is correct
52 Correct 154 ms 222548 KB Output is correct
53 Correct 155 ms 223320 KB Output is correct
54 Correct 155 ms 223312 KB Output is correct
55 Correct 148 ms 220752 KB Output is correct
56 Correct 119 ms 217688 KB Output is correct
57 Correct 156 ms 224088 KB Output is correct
58 Correct 140 ms 220380 KB Output is correct
59 Correct 99 ms 211536 KB Output is correct
60 Correct 96 ms 211544 KB Output is correct
61 Correct 910 ms 321408 KB Output is correct
62 Correct 968 ms 297176 KB Output is correct
63 Correct 840 ms 270428 KB Output is correct
64 Correct 703 ms 294172 KB Output is correct
65 Correct 749 ms 298536 KB Output is correct
66 Correct 720 ms 294320 KB Output is correct
67 Correct 694 ms 278760 KB Output is correct
68 Correct 711 ms 276472 KB Output is correct
69 Correct 754 ms 281220 KB Output is correct
70 Correct 617 ms 269864 KB Output is correct
71 Correct 553 ms 267296 KB Output is correct
72 Correct 608 ms 271688 KB Output is correct
73 Correct 603 ms 268176 KB Output is correct
74 Correct 545 ms 271692 KB Output is correct
75 Correct 597 ms 270072 KB Output is correct
76 Correct 127 ms 222544 KB Output is correct
77 Correct 516 ms 268608 KB Output is correct
78 Correct 510 ms 265264 KB Output is correct
79 Correct 102 ms 211540 KB Output is correct
80 Correct 105 ms 211760 KB Output is correct