oj.uz

Submission #1013351

# Submission time Handle Problem Language Result Execution time Memory
1013351 2024-07-03T12:41:07 Z PCTprobability Abracadabra (CEOI22_abracadabra) C++17
35 / 100
 3000 ms 36168 KB 
#include <bits/stdc++.h>
using namespace std;
/*#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif*/
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define endl "\n"
typedef pair<int, int> Pii;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(x) begin(x), end(x)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(s) (s).begin(),(s).end()
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define se second
#define pb push_back
#define P pair<ll,ll>
#define PQminll priority_queue<ll, vector<ll>, greater<ll>>
#define PQmaxll priority_queue<ll,vector<ll>,less<ll>>
#define PQminP priority_queue<P, vector<P>, greater<P>>
#define PQmaxP priority_queue<P,vector<P>,less<P>>
#define NP next_permutation
#define die(a) {cout<<a<<endl;return 0;}
#define dier(a) {return a;}
//const ll mod = 1000000009;
const ll mod = 998244353;
//const ll mod = 1000000007;
const ll inf = 4100000000000000000ll;
const ld eps = ld(0.00000000001);
static const long double pi = 3.141592653589793;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
template<class T>auto min(const T& a){ return *min_element(all(a)); }
template<class T>auto max(const T& a){ return *max_element(all(a)); }
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>bool chmax(T &a,const T b) { if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a,const T b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;}
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}
P hyou(P a){ll x=fastgcd(abs(a.fi),abs(a.se));a.fi/=x;a.se/=x;if(a.se<0){a.fi*=-1;a.se*=-1;}return a;}
P Pplus(P a,P b){ return hyou({a.fi*b.se+b.fi*a.se,a.se*b.se});}
P Ptimes(P a,ll b){ return hyou({a.fi*b,a.se});}
P Ptimes(P a,P b){ return hyou({a.fi*b.fi,a.se*b.se});}
P Pminus(P a,P b){ return hyou({a.fi*b.se-b.fi*a.se,a.se*b.se});}
P Pgyaku(P a){ return hyou({a.se,a.fi});}

void cincout(){
  ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
  cout<< fixed << setprecision(15);
}
struct segtree{
  vector<ll> node;
  ll n;
  segtree(ll _n){
    n=1;
    while(n<_n) n*=2;
    node.resize(2*n);
  }
  void set(ll i,ll v){
    i+=n;
    node[i]=v;
    while(i){
      i/=2;
      node[i]=node[2*i]+node[2*i+1];
    }
  }
  ll prod(ll l,ll r,ll a,ll b,ll k){
    if(r<=a||b<=l) return 0;
    if(l<=a&&b<=r) return node[k];
    return prod(l,r,a,(a+b)/2,2*k)+prod(l,r,(a+b)/2,b,2*k+1);
  }
  ll prod(ll l,ll r){
    return prod(l,r,0,n,1);
  }
};
int main(){
  cincout();
  ll n,q;
  cin>>n>>q;
  n/=2;
  vector<ll> a(2*n);
  vcin(a);
  for(auto &e:a) e--;
  vector<vector<P>> t(2*n+1);
  for(int i=0;i<q;i++){
    ll tm,x;
    cin>>tm>>x;
    chmin(tm,2*n);
    t[tm].pb({x,i});
  }
  vector<ll> ans(q);
  vector<ll> rev(2*n);
  for(int i=0;i<2*n;i++) rev[a[i]]=i;
  ll now=1,id=0;
  segtree seg(2*n);
  for(int i=1;i<2*n;i++){
    if(a[id]<a[i]){
      seg.set(a[id],now);
      now=1;
      id=i;
    }
    else now++;
  }
  seg.set(a[id],now);
  for(int _=0;_<=2*n;_++){
    if(_){
      for(auto e:t[_]){
        ll sm=0;
        ll ok=2*n-1,ng=-1;
        while(abs(ok-ng)>1){
          ll mid=(ok+ng)/2;
          if(seg.prod(0,mid+1)>=e.fi) ok=mid;
          else ng=mid;
        }
        ans[e.se]=a[rev[ok]+e.fi-seg.prod(0,ok)-1]+1;
      }
    }
    else{
      for(auto e:t[_]){
        ans[e.se]=a[e.fi-1]+1;
      }
    }
    ll sm=0;
    ll ok=2*n-1,ng=-1;
    while(abs(ok-ng)>1){
      ll mid=(ok+ng)/2;
      if(seg.prod(0,mid+1)>=n) ok=mid;
      else ng=mid;
    }
    ll l=rev[ok]+n-seg.prod(0,ok),r=rev[ok]+seg.prod(ok,ok+1)-1;
    seg.set(ok,n-seg.prod(0,ok));
    if(l>r) continue;
    ll now=1,id=l;
    for(int j=l+1;j<=r;j++){
      if(a[id]<a[j]){
        seg.set(a[id],now);
        now=1;
        id=j;
      }
      else now++;
    }
    seg.set(a[id],now);
  }
  for(auto e:ans) cout<<e<<endl;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:135:12: warning: unused variable 'sm' [-Wunused-variable]
  135 |         ll sm=0;
      |            ^~
Main.cpp:150:8: warning: unused variable 'sm' [-Wunused-variable]
  150 |     ll sm=0;
      |        ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 31948 KB Output is correct
2 Correct 517 ms 30156 KB Output is correct
3 Correct 440 ms 29388 KB Output is correct
4 Correct 436 ms 27444 KB Output is correct
5 Correct 456 ms 32720 KB Output is correct
6 Correct 448 ms 31208 KB Output is correct
7 Correct 440 ms 34736 KB Output is correct
8 Correct 424 ms 34568 KB Output is correct
9 Correct 443 ms 33736 KB Output is correct
10 Correct 441 ms 33668 KB Output is correct
11 Correct 442 ms 33732 KB Output is correct
12 Correct 377 ms 31464 KB Output is correct
13 Correct 404 ms 31980 KB Output is correct
14 Correct 489 ms 35764 KB Output is correct
15 Correct 384 ms 33648 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 139 ms 31840 KB Output is correct
18 Correct 257 ms 31524 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 36168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 10580 KB Output is correct
2 Correct 243 ms 10324 KB Output is correct
3 Correct 1002 ms 10088 KB Output is correct
4 Correct 193 ms 10064 KB Output is correct
5 Correct 206 ms 10316 KB Output is correct
6 Correct 187 ms 10064 KB Output is correct
7 Correct 212 ms 10324 KB Output is correct
8 Correct 194 ms 11604 KB Output is correct
9 Correct 206 ms 11604 KB Output is correct
10 Correct 196 ms 11600 KB Output is correct
11 Correct 212 ms 11860 KB Output is correct
12 Correct 196 ms 11600 KB Output is correct
13 Correct 184 ms 11312 KB Output is correct
14 Correct 202 ms 11600 KB Output is correct
15 Correct 177 ms 11344 KB Output is correct
16 Correct 93 ms 6744 KB Output is correct
17 Correct 106 ms 10384 KB Output is correct
18 Correct 123 ms 10480 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 31948 KB Output is correct
2 Correct 517 ms 30156 KB Output is correct
3 Correct 440 ms 29388 KB Output is correct
4 Correct 436 ms 27444 KB Output is correct
5 Correct 456 ms 32720 KB Output is correct
6 Correct 448 ms 31208 KB Output is correct
7 Correct 440 ms 34736 KB Output is correct
8 Correct 424 ms 34568 KB Output is correct
9 Correct 443 ms 33736 KB Output is correct
10 Correct 441 ms 33668 KB Output is correct
11 Correct 442 ms 33732 KB Output is correct
12 Correct 377 ms 31464 KB Output is correct
13 Correct 404 ms 31980 KB Output is correct
14 Correct 489 ms 35764 KB Output is correct
15 Correct 384 ms 33648 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 139 ms 31840 KB Output is correct
18 Correct 257 ms 31524 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3026 ms 36168 KB Time limit exceeded
22 Halted 0 ms 0 KB -