oj.uz

Submission #957741

# Submission time Handle Problem Language Result Execution time Memory
957741 2024-04-04T09:01:55 Z 8pete8 Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 877 ms 314844 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 pos=0,xx=x;
	for(int i=lg;i>=0;i--){
		if(pos+(1ll<<i)<=n&&x-t.fwk[pos+(1ll<<i)]>0){
			pos+=(1ll<<i);
			x-=t.fwk[pos];
		}
	}
	pos++;
	int y=(xx)-(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:133: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]
  133 |   if(com[a.f].size()<a.s)break;
      |                     ^
Main.cpp:134: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]
  134 |   if(a.s==com[a.f].size())break;
      |      ~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 249508 KB Output is correct
2 Correct 529 ms 249432 KB Output is correct
3 Correct 450 ms 248072 KB Output is correct
4 Correct 452 ms 247488 KB Output is correct
5 Correct 440 ms 249180 KB Output is correct
6 Correct 402 ms 247764 KB Output is correct
7 Correct 416 ms 249272 KB Output is correct
8 Correct 411 ms 247868 KB Output is correct
9 Correct 411 ms 247412 KB Output is correct
10 Correct 429 ms 248236 KB Output is correct
11 Correct 410 ms 248144 KB Output is correct
12 Correct 397 ms 247124 KB Output is correct
13 Correct 454 ms 248048 KB Output is correct
14 Correct 437 ms 248580 KB Output is correct
15 Correct 447 ms 248928 KB Output is correct
16 Correct 131 ms 211540 KB Output is correct
17 Correct 388 ms 247672 KB Output is correct
18 Correct 479 ms 247376 KB Output is correct
19 Correct 117 ms 211764 KB Output is correct
20 Correct 108 ms 211572 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 314844 KB Output is correct
2 Correct 498 ms 290900 KB Output is correct
3 Correct 421 ms 257756 KB Output is correct
4 Correct 437 ms 281844 KB Output is correct
5 Correct 467 ms 285068 KB Output is correct
6 Correct 434 ms 281884 KB Output is correct
7 Correct 431 ms 272796 KB Output is correct
8 Correct 438 ms 270444 KB Output is correct
9 Correct 441 ms 269708 KB Output is correct
10 Correct 417 ms 263760 KB Output is correct
11 Correct 369 ms 256084 KB Output is correct
12 Correct 406 ms 259204 KB Output is correct
13 Correct 417 ms 262108 KB Output is correct
14 Correct 395 ms 259144 KB Output is correct
15 Correct 434 ms 263616 KB Output is correct
16 Correct 132 ms 222008 KB Output is correct
17 Correct 451 ms 263900 KB Output is correct
18 Correct 370 ms 254520 KB Output is correct
19 Correct 201 ms 230820 KB Output is correct
20 Correct 196 ms 231764 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 248660 KB Output is correct
2 Correct 206 ms 237092 KB Output is correct
3 Correct 199 ms 224084 KB Output is correct
4 Correct 176 ms 228864 KB Output is correct
5 Correct 224 ms 246536 KB Output is correct
6 Correct 169 ms 230736 KB Output is correct
7 Correct 187 ms 239440 KB Output is correct
8 Correct 173 ms 231500 KB Output is correct
9 Correct 187 ms 239116 KB Output is correct
10 Correct 156 ms 223572 KB Output is correct
11 Correct 178 ms 223948 KB Output is correct
12 Correct 175 ms 223604 KB Output is correct
13 Correct 162 ms 224256 KB Output is correct
14 Correct 174 ms 224240 KB Output is correct
15 Correct 155 ms 221776 KB Output is correct
16 Correct 125 ms 218200 KB Output is correct
17 Correct 158 ms 225040 KB Output is correct
18 Correct 154 ms 221352 KB Output is correct
19 Correct 111 ms 211608 KB Output is correct
20 Correct 122 ms 211540 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 249508 KB Output is correct
2 Correct 529 ms 249432 KB Output is correct
3 Correct 450 ms 248072 KB Output is correct
4 Correct 452 ms 247488 KB Output is correct
5 Correct 440 ms 249180 KB Output is correct
6 Correct 402 ms 247764 KB Output is correct
7 Correct 416 ms 249272 KB Output is correct
8 Correct 411 ms 247868 KB Output is correct
9 Correct 411 ms 247412 KB Output is correct
10 Correct 429 ms 248236 KB Output is correct
11 Correct 410 ms 248144 KB Output is correct
12 Correct 397 ms 247124 KB Output is correct
13 Correct 454 ms 248048 KB Output is correct
14 Correct 437 ms 248580 KB Output is correct
15 Correct 447 ms 248928 KB Output is correct
16 Correct 131 ms 211540 KB Output is correct
17 Correct 388 ms 247672 KB Output is correct
18 Correct 479 ms 247376 KB Output is correct
19 Correct 117 ms 211764 KB Output is correct
20 Correct 108 ms 211572 KB Output is correct
21 Correct 509 ms 314844 KB Output is correct
22 Correct 498 ms 290900 KB Output is correct
23 Correct 421 ms 257756 KB Output is correct
24 Correct 437 ms 281844 KB Output is correct
25 Correct 467 ms 285068 KB Output is correct
26 Correct 434 ms 281884 KB Output is correct
27 Correct 431 ms 272796 KB Output is correct
28 Correct 438 ms 270444 KB Output is correct
29 Correct 441 ms 269708 KB Output is correct
30 Correct 417 ms 263760 KB Output is correct
31 Correct 369 ms 256084 KB Output is correct
32 Correct 406 ms 259204 KB Output is correct
33 Correct 417 ms 262108 KB Output is correct
34 Correct 395 ms 259144 KB Output is correct
35 Correct 434 ms 263616 KB Output is correct
36 Correct 132 ms 222008 KB Output is correct
37 Correct 451 ms 263900 KB Output is correct
38 Correct 370 ms 254520 KB Output is correct
39 Correct 201 ms 230820 KB Output is correct
40 Correct 196 ms 231764 KB Output is correct
41 Correct 213 ms 248660 KB Output is correct
42 Correct 206 ms 237092 KB Output is correct
43 Correct 199 ms 224084 KB Output is correct
44 Correct 176 ms 228864 KB Output is correct
45 Correct 224 ms 246536 KB Output is correct
46 Correct 169 ms 230736 KB Output is correct
47 Correct 187 ms 239440 KB Output is correct
48 Correct 173 ms 231500 KB Output is correct
49 Correct 187 ms 239116 KB Output is correct
50 Correct 156 ms 223572 KB Output is correct
51 Correct 178 ms 223948 KB Output is correct
52 Correct 175 ms 223604 KB Output is correct
53 Correct 162 ms 224256 KB Output is correct
54 Correct 174 ms 224240 KB Output is correct
55 Correct 155 ms 221776 KB Output is correct
56 Correct 125 ms 218200 KB Output is correct
57 Correct 158 ms 225040 KB Output is correct
58 Correct 154 ms 221352 KB Output is correct
59 Correct 111 ms 211608 KB Output is correct
60 Correct 122 ms 211540 KB Output is correct
61 Correct 738 ms 314568 KB Output is correct
62 Correct 877 ms 291148 KB Output is correct
63 Correct 733 ms 264308 KB Output is correct
64 Correct 588 ms 288116 KB Output is correct
65 Correct 607 ms 292364 KB Output is correct
66 Correct 590 ms 288336 KB Output is correct
67 Correct 510 ms 272592 KB Output is correct
68 Correct 550 ms 270420 KB Output is correct
69 Correct 550 ms 275264 KB Output is correct
70 Correct 512 ms 264420 KB Output is correct
71 Correct 483 ms 261848 KB Output is correct
72 Correct 506 ms 266048 KB Output is correct
73 Correct 469 ms 262800 KB Output is correct
74 Correct 496 ms 265920 KB Output is correct
75 Correct 503 ms 264136 KB Output is correct
76 Correct 141 ms 222416 KB Output is correct
77 Correct 460 ms 264220 KB Output is correct
78 Correct 456 ms 260944 KB Output is correct
79 Correct 106 ms 211536 KB Output is correct
80 Correct 105 ms 211540 KB Output is correct