oj.uz

답안 #1013335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013335 2024-07-03T12:22:45 Z PCTprobability Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 780 ms 42156 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);
}

int main(){
  cincout();
  ll n,q;
  cin>>n>>q;
  assert(n<=1000);
  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;
  vector<ll> seg(2*n);
  for(int i=1;i<2*n;i++){
    if(a[id]<a[i]){
      seg[a[id]]+=now;
      now=1;
      id=i;
    }
    else now++;
  }
  seg[a[id]]+=now;
  for(int _=0;_<=2*n;_++){
    if(_){
      for(auto e:t[_]){
        ll sm=0;
        for(int j=0;j<2*n;j++){
          if(sm+seg[j]>=e.fi){
            ans[e.se]=a[rev[j]+e.fi-sm-1]+1;
            break;
          }
          sm+=seg[j];
        }
      }
    }
    else{
      for(auto e:t[_]){
        ans[e.se]=a[e.fi-1]+1;
      }
    }
    ll sm=0;
    for(int i=0;i<2*n;i++){
      if(sm+seg[i]>=n){
        ll l=rev[i]+n-sm,r=rev[i]+seg[i]-1;
        if(l>r) break;
        ll now=1,id=l;
        for(int j=l+1;j<=r;j++){
          if(a[id]<a[j]){
            seg[a[id]]+=now;
            now=1;
            id=j;
          }
          else now++;
        }
        seg[a[id]]+=now;
        seg[i]=n-sm;
        break;
      }
      sm+=seg[i];
    }
  }
  for(auto e:ans) cout<<e<<endl;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 518 ms 39632 KB Output is correct
2 Correct 530 ms 37576 KB Output is correct
3 Correct 473 ms 36560 KB Output is correct
4 Correct 780 ms 33596 KB Output is correct
5 Correct 730 ms 39884 KB Output is correct
6 Correct 671 ms 37612 KB Output is correct
7 Correct 688 ms 42156 KB Output is correct
8 Correct 701 ms 35688 KB Output is correct
9 Correct 732 ms 35040 KB Output is correct
10 Correct 654 ms 34692 KB Output is correct
11 Correct 706 ms 34744 KB Output is correct
12 Correct 631 ms 32344 KB Output is correct
13 Correct 681 ms 33364 KB Output is correct
14 Correct 697 ms 37036 KB Output is correct
15 Correct 760 ms 35040 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 127 ms 32672 KB Output is correct
18 Correct 429 ms 32604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 518 ms 39632 KB Output is correct
2 Correct 530 ms 37576 KB Output is correct
3 Correct 473 ms 36560 KB Output is correct
4 Correct 780 ms 33596 KB Output is correct
5 Correct 730 ms 39884 KB Output is correct
6 Correct 671 ms 37612 KB Output is correct
7 Correct 688 ms 42156 KB Output is correct
8 Correct 701 ms 35688 KB Output is correct
9 Correct 732 ms 35040 KB Output is correct
10 Correct 654 ms 34692 KB Output is correct
11 Correct 706 ms 34744 KB Output is correct
12 Correct 631 ms 32344 KB Output is correct
13 Correct 681 ms 33364 KB Output is correct
14 Correct 697 ms 37036 KB Output is correct
15 Correct 760 ms 35040 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 127 ms 32672 KB Output is correct
18 Correct 429 ms 32604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 1 ms 604 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -