oj.uz

Submission #654619

# Submission time Handle Problem Language Result Execution time Memory
654619 2022-10-31T23:32:32 Z sunwukong123 Abracadabra (CEOI22_abracadabra) C++14
25 / 100
 263 ms 57832 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 	
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 200005;
int n,q;
map<int,int> val;
int A[MAXN];
int nxt[MAXN];
int where[MAXN];
int fw[MAXN];
vector<pi> Qs[MAXN];
int out[MAXN];
set<int> s;
void update(int x, int nval) {
	for(;x<MAXN;x+=x&-x)fw[x]+=nval;
}
int sum(int x) {
	int r=0;
	for(;x;x-=x&-x)r+=fw[x];
	return r;
}
int kth(int &k){
    int csum = 0;
    int pos = 0;
    for (int i = 20; i >= 0; i--){
        if (pos + (1 << i) < n && fw[pos + (1 << i)] < k){
            pos += (1 << i);
            k-=fw[pos];
        }
    }
    return pos + 1;
}


int32_t main() 
{
	IAMSPEED
	cin >> n >> q;
	FOR(i,1,n) cin >> A[i];
	FOR(qq,1,q) {
		int t, x; cin >> t >> x;
		Qs[min(t,n)].pb(pi(x,qq));
	}
	FOR(i,1,n) where[A[i]] = i;
	stack<int> st;
	DEC(i,n,1) {
		while(st.size() && A[i] > st.top())st.pop();
		if(st.empty())nxt[i]=n+1;
		else {
			nxt[i]=where[st.top()];
		}
		st.push(A[i]);
	}
	
	int it=1;
	while(it<=n) {

		update(A[it], nxt[it] - it);
		it=nxt[it];
	}
	FOR(ti,0,n) {

		for(auto query:Qs[ti]) {
			int val=kth(query.f);
			out[query.s]=A[where[val]+query.f-1];
			
		}
		int m=n/2+1;
		int val=kth(m);
		if(m==1) continue;
		int len=sum(val) - sum(val-1);
		int ed=where[val] + len;
		update(val, -len + m - 1);
		
		for(int id=where[val]+m-1;id<ed;id=nxt[id]) {
			update(A[id], min(nxt[id],ed) - id);
		}
		
		
	}
	FOR(i,1,q)cout<<out[i]<<"\n";
	
}

Compilation message

Main.cpp: In function 'long long int kth(long long int&)':
Main.cpp:62:9: warning: unused variable 'csum' [-Wunused-variable]
   62 |     int csum = 0;
      |         ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 56524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 263 ms 57832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12220 KB Output is correct
2 Correct 73 ms 14092 KB Output is correct
3 Correct 71 ms 13748 KB Output is correct
4 Correct 48 ms 13196 KB Output is correct
5 Correct 67 ms 13100 KB Output is correct
6 Correct 53 ms 13192 KB Output is correct
7 Correct 60 ms 12988 KB Output is correct
8 Correct 62 ms 13000 KB Output is correct
9 Correct 55 ms 13384 KB Output is correct
10 Correct 46 ms 13228 KB Output is correct
11 Correct 46 ms 13128 KB Output is correct
12 Correct 41 ms 13272 KB Output is correct
13 Correct 50 ms 13012 KB Output is correct
14 Correct 45 ms 13476 KB Output is correct
15 Correct 41 ms 12600 KB Output is correct
16 Correct 15 ms 8480 KB Output is correct
17 Correct 51 ms 12564 KB Output is correct
18 Correct 35 ms 11284 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 56524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -