QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#755685	#9559. The Tower	ucup-team112^#	AC ✓	764ms	116640kb	C++20	18.4kb	2024-11-16 17:53:17	2024-11-20 08:47:31

Judging History

你现在查看的是最新测评结果

[2024-11-20 08:47:31]
自动重测本题所有获得100分的提交记录

测评结果：AC
用时：764ms
内存：116640kb

查看

[2024-11-20 08:41:35]
hack成功，自动添加数据
(/hack/1205)

[2024-11-16 17:53:24]
评测

测评结果：100
用时：740ms
内存：116708kb

查看

[2024-11-16 17:53:17]
提交

answer


//#define _GLIBCXX_DEBUG

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;


#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif

#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)

namespace template_tute{
  using ll = long long;
  using ld = long double;
  const ll MOD1 = 1e9+7;
  const ll MOD9 = 998244353;
  const ll INF = 4.1e18;
  using P = pair<ll, ll>;
  template<typename T> using PQ = priority_queue<T>;
  template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
  template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
  template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
  ll median(ll a,ll b, ll c){return a+b+c-max<ll>({a,b,c})-min<ll>({a,b,c});}
  void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
  void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
  void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
  template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
  template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};  
  template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
  template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
  template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
  template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
  template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
  template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
  template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
  template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
  vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
  template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
  template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
  template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
  template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
  template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
    auto tmp = v;
    for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
  }
  template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
    rearrange(ord, head);
    rearrange(ord, tail...);
  }
  template<typename T> vector<int> ascend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
    return ord;
  }
  template<typename T> vector<int> descend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
    return ord;
  }
  template<typename T> vector<T> inv_perm(const vector<T>&ord){
    vector<T>inv(ord.size());
    for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
    return inv;
  }
  ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
  ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
  ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
  ll modulo(ll n,ll d){return (n%d+d)%d;};
  template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
  template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
  template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
  template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
  //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  int popcount(ll x){return __builtin_popcountll(x);};
  int poplow(ll x){return __builtin_ctzll(x);};
  int pophigh(ll x){return 63 - __builtin_clzll(x);};
  template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
  template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
  ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
  ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
  ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
  std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
      __uint128_t tmp = value < 0 ? -value : value;
      char buffer[128];
      char *d = std::end(buffer);
      do {
        --d;
        *d = "0123456789"[tmp % 10];
        tmp /= 10;
      } while (tmp != 0);
      if (value < 0) {
        --d;
        *d = '-';
      }
      int len = std::end(buffer) - d;
      if (dest.rdbuf()->sputn(d, len) != len) {
        dest.setstate(std::ios_base::badbit);
      }
    }
    return dest;
  }
  namespace converter{
    int dict[500];
    const string lower="abcdefghijklmnopqrstuvwxyz";
    const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string digit="0123456789";
    const string digit1="123456789";
    void regi_str(const string &t){
      for(int i=0;i<t.size();i++){
        dict[t[i]]=i;
      }
    }
    void regi_int(const string &t){
      for(int i=0;i<t.size();i++){
        dict[i]=t[i];
      }
    }
    vector<int>to_int(const string &s,const string &t){
      regi_str(t);
      vector<int>ret(s.size());
      for(int i=0;i<s.size();i++){
        ret[i]=dict[s[i]];
      }
      return ret;
    }
    vector<int>to_int(const string &s){
      auto t=s;
      sort(t.begin(),t.end());
      t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    
    vector<vector<int>>to_int(const vector<string>&s,const string &t){
      regi_str(t);
      vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
      for(int i=0;i<s.size();i++){
        for(int j=0;j<s[0].size();j++){
          ret[i][j]=dict[s[i][j]];
        }
      }
      return ret;
    }
    vector<vector<int>>to_int(const vector<string>&s){
      string t;
      for(int i=0;i<s.size();i++){
        t+=s[i];
      }
      sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    string to_str(const vector<int>&s,const string &t){
      regi_int(t);
      string ret;
      for(auto z:s)ret+=dict[z];
      return ret;
    }
    vector<string> to_str(const vector<vector<int>>&s,const string &t){
      regi_int(t);
      vector<string>ret(s.size());
      for(int i=0;i<s.size();i++){
        for(auto z:s[i])ret[i]+=dict[z];
      }
      return ret;
    }
  }
  template< typename T = int >
  struct edge {
    int to;
    T cost;
    int id;
    edge():to(-1),id(-1){};
    edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
    operator int() const { return to; }
  };

  template<typename T>
  using Graph = vector<vector<edge<T>>>;
  template<typename T>
  Graph<T>revgraph(const Graph<T> &g){
    Graph<T>ret(g.size());
    for(int i=0;i<g.size();i++){
      for(auto e:g[i]){
        int to = e.to;
        e.to = i;
        ret[to].push_back(e);
      }
    }
    return ret;
  }
  template<typename T>
  Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
    Graph<T> ret(n);
    for(int es = 0; es < m; es++){
      int u,v;
      T w=1;
      cin>>u>>v;u-=indexed,v-=indexed;
      if(weighted)cin>>w;
      ret[u].emplace_back(v,w,es);
      if(!directed)ret[v].emplace_back(u,w,es);
    }
    return ret;
  }
  template<typename T>
  Graph<T> readParent(int n,int indexed=1,bool directed=true){
    Graph<T>ret(n);
    for(int i=1;i<n;i++){
      int p;cin>>p;
      p-=indexed;
      ret[p].emplace_back(i);
      if(!directed)ret[i].emplace_back(p);
    }
    return ret;
  }
}
using namespace template_tute;

template<typename Key, typename Val>
struct KeyValueTreap{
  mt19937 mt;
  struct Node{
    Node* ch[2];
    Node* par;
    int pri, sz = 1;
    int aff = -1;
    Key key;
    Val val, sum;;
    Node(){}
    Node(Key key, Val val,int pri):key(key),val(val),sum(val),pri(pri),ch{nullptr, nullptr},par{nullptr}{};
  };
  int nxt = 0;
  Val M1 = 0;
  Node* root = nullptr;
  Val f(Val x, Val y){
    return x+y;
  }
  KeyValueTreap():mt(99){
  }
  KeyValueTreap(int x):mt(x){
    //cout<<"debug"<<endl;
  }
    int gen(){
      return uniform_int_distribution<int>(0,1<<30)(mt);
    }
    int count(Node *t){return !t ? 0 : t->sz;};
    Val sum(Node *t){return !t ? M1 : t->sum;};
    Node* update(Node* t){
      if(!t)return t;
      t->sz = count(t->ch[0]) + count(t->ch[1]) + 1;
      t->sum = f(sum(t->ch[0]), f(t->val, sum(t->ch[1])));
      return t;
    }
    template<typename ... Args>
    Node* merge(Node *l, Args... rest){
      Node *r=merge(rest...);
      if(!l || !r)return !l ? r : l;
      if(l->pri > r->pri){
        if(l->ch[1])l->ch[1]->par = nullptr;
        l->ch[1] = merge(l->ch[1], r);
        if(l->ch[1])l->ch[1]->par = l;
        return update(l);
      }
      else{
        if(r->ch[0])r->ch[0]->par = nullptr;
        r->ch[0] = merge(l, r->ch[0]);
        if(r->ch[0])r->ch[0]->par = r;
        return update(r);
      }
    }
    Node *merge(Node *l){
      return l;
    }
    using PN = pair<Node*, Node*>;
    PN split(Node* t, int k){ //[0,k),[k,n)
      if(!t) return make_pair(nullptr, nullptr);
      if(k <= count(t->ch[0])){
        PN s = split(t->ch[0], k);
        if(t->ch[0])t->ch[0]->par = nullptr;
        t->ch[0] = s.second;
        if(s.second)s.second->par = t;
        return make_pair(s.first, update(t));
      }
      else{
        PN s = split(t->ch[1], k - count(t->ch[0]) - 1);
        if(t->ch[1])t->ch[1]->par = nullptr;
        t->ch[1] = s.first;
        if(s.first)s.first->par = t;
        return make_pair(update(t), s.second);
      }
    }
    tuple<Node*,Node*,Node*> split3(Node *&t, int l, int r){//[0,l),[l,r),[r,n)
      PN sp = split(t,r);
      PN sp2 = split(sp.first,l);
      return make_tuple(sp2.first, sp2.second, sp.second);
    }
    //t内で初めてcheckを満たすような位置がt内で何番目か
    //満たさなければsize
    template<typename F>
    int _find_first(Node *t, const F &check){
      int ret = 0;
      Val now = M1;
      if(!check(sum(t)))return count(t);
      while(1){
        if(!t)return ret;
        if(check(f(now, sum(t->ch[0])))){
          t = t->ch[0];
        }
        else{
          now = f(now, sum(t->ch[0]));
          ret += count(t->ch[0]);
          now = f(now, t->val);
          if(check(now))return ret;
          ret++;
          t = t->ch[1];
        }
      }
    }
    //t内で初めてcheckを満たすような位置がt内で何番目か
    //満たさなければ-1
    template<typename F>
    int _find_last(Node *t, const F &check){
      int ret = count(t);
      Val now = M1;
      if(!check(sum(t)))return -1;
      while(1){
        if(!t)return ret;
        if(check(f(sum(t->ch[1]),now))){
          t = t->ch[1];
        }
        else{
          now = f(sum(t->ch[1]),now);
          ret -= count(t->ch[1]);
          now = f(t->val, now);
          if(check(now))return ret;
          ret--;
          t = t->ch[0];
        }
      }
    }
    int _count_lower(Node* t, Key key){
      int ret = 0;
      while(t){
        if(t->key >= key)t = t->ch[0];
        else{
          ret += count(t->ch[0]) + 1;
          t = t->ch[1];
        }
      }
      return ret;
    }
    void update(Key key, Val val, Node* t){
      if(t->key == key){
        t->val = val;
        update(t);
      }
      else if(t->key > key){
        update(key, val, t->ch[0]);
        update(t);
      }
      else{
        update(key, val, t->ch[1]);
        update(t);
      }
    }
    Node* get(Node* t, Key key){
      if(!t)return nullptr;
      if(t->key == key)return t;
      if(t->key > key)return get(t->ch[0], key);
      return get(t->ch[1], key);
    }
    Node* get_kth(Node* t, int k){
      while(t){
        if(count(t->ch[0]) == k)return t;
        if(count(t->ch[0]) > k)t = t->ch[0];
        else{
          k -= count(t->ch[0]) + 1;
          t = t->ch[1];
        }
      }
      return nullptr;
    }
    vector<Node*>enumerate(Node *t  ){
      vector<Node*>ret;
      vector<string>db;
      auto dfs=[&](auto &&f, Node *nt)->void {
        if(!nt)return;
        for(int i=0;i<2;i++){
          if(i==1){
            db.push_back("["+to_string(nt->key)+"]="+to_string(nt->val));
            ret.push_back(nt);
          }
          if(nt->ch[i])f(f, nt->ch[i]);
        }
      };
      dfs(dfs, t);
      debug(db,db.size(),"|");
      return ret;
    }
    //key未満の個数
    int count_lower(Key r){
      return _count_lower(root, r);
    }

    //Key指定で挿入
    void insert(Key key, Val val){
      int k = _count_lower(root, key);
      PN sp = split(root,k);
      sp.first = merge(sp.first, new Node(key, val, gen()));
      root = merge(sp.first, sp.second);
    }

    //Key指定で削除（複数ある場合は一つ）
    void erase(Key key){
      int k = _count_lower(root, key);
      auto [l, m, r] = split3(root, k, k+1);
      root = merge(l, r);
    }

    //Key指定でupdate（複数ある場合は一つupdate）
    void update(Key key, Val val){
      update(key, val, root);
    }

    //keyのNodeを取得、なければnullptr
    Node* get(Key key){
      return get(root, key);
    }

    //k番目(0-indexed)のNodeを取得、なければnullptr
    Node* get_kth(int k){
      return get_kth(root, k);
    }

    int size(Node *t){
      return count(t);
    }
    //[k,r]がcheckを満たす最初のr、なければsize
    template<typename F>
    int find_first(const F &check, int k){
      auto [l, r] = split(root, k);
      int ret = _find_first(r, check);
      root = merge(l, r);
      return k + ret;
    }
    //[l,k)がcheckを満たす最後のl、なければ-1
    template<typename F>
    int find_last(const F &check, int k){
      auto [l, r] = split(root, k);
      int ret = _find_last(l, check);
      root = merge(l, r);
      return ret;
    }
    vector<Node*>enumerate(){
      return enumerate(root);
    }
};


void solve(){
	ll res=0,buf=0;
  bool judge = true;

  ll q;cin>>q;
  using K=KeyValueTreap<ll,ll>::Node;
  KeyValueTreap<ll,ll>tr;
  vector<K*>tv(1);
  const ll inf=2e15;
  tv[0]=new K(1,inf,tr.gen());
  tv[0]=tr.merge(tv[0],new K(inf,inf,tr.gen()));
  tv[0]->aff=0;
  map<ll,K*>mp;
  mp[1]=tv[0];
  while(q--){
    // OUT(q);
    // rep(i,0,tv.size()){
    //   tr.enumerate(tv[i]);
    // }
    ll t;cin>>t;
    if(t==1){
      ll k;cin>>k;
      ll idx=tv.size();
      tv.PB(nullptr);
      ll pos=tr._find_first(tv[0],[&](ll x){return x>=k;});
      auto [l,m,r]=tr.split3(tv[0],pos,pos+1);
      ll presum=tr.sum(l);
      auto ml=new K(m->key,k-presum,tr.gen());
      mp[m->key]=ml;
      K* mr=nullptr;
      if(presum+tr.sum(m)>k){
        ll key=m->key+k-presum;
        mr=new K(key,tr.sum(m)-(k-presum),tr.gen());
        mp[key]=mr;
      }
      tv[idx]=tr.merge(l,ml);
      tv[idx]->aff=idx;
      tv[0]=tr.merge(mr,r);
      tv[0]->aff=0;
    }
    if(t==2){
      ll u;cin>>u;
      auto iu=tv[u];
      while(iu){
        auto mikey=tr.get_kth(iu,0)->key;
        int pos=tr._count_lower(tv[0],mikey);
        auto [l,r]=tr.split(tv[0],pos);
        //OUT(pos,iu->key);
        // tr.enumerate(l);
        // tr.enumerate(r);
        auto i0=tr.get_kth(r,0);
        //tr.enumerate(iu);
        int sz=tr._count_lower(iu,i0->key);
        auto [ins,rem] = tr.split(iu,sz);
        //OUT(i0->key,pos,sz,tr.size(ins));
        //tr.enumerate(ins);
        //tr.enumerate(rem);
        iu=rem;
        tv[0]=tr.merge(l,ins,r);
        tv[0]->aff=0;
      }
      tv[u]=nullptr;
    }
    if(t==3){
      ll pos;cin>>pos;
      auto it=--mp.upper_bound(pos);
      auto p=it->second;
      while(p->par){
        p=p->par;
      }
      cout<<p->aff<<endl;
    }
  }
  // OUT(q);
  // rep(i,0,tv.size()){
  //   OUT(i);
  //   tr.enumerate(tv[i]);
  // }
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  int T = 1;
  //cin>>T;
  while(T--){
    solve();
  }
  return 0;
}

Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3652kb

input:

output:

2
0
3

result:

ok 3 number(s): "2 0 3"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3872kb

input:

output:

result:

ok 164 numbers

Test #4:

score: 0

Accepted

time: 1ms

memory: 3920kb

input:

500
3 1
3 1
3 1
3 1
3 1
1 4412412
1 10247266
1 14616289
3 13925896
1 44094358
2 4
3 16963583
1 29167079
1 71445446
3 121523866
1 9541088
2 6
2 7
3 143236216
2 2
3 156313828
1 33267424
3 100714325
3 15092860
3 89601770
2 8
3 201789970
1 30507527
2 5
1 67021830
3 234973560
1 10823444
1 19147051
1 7218...

output:

result:

ok 174 numbers

Test #5:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

500
3 1
3 1
3 1
1 320269189
1 948169162
1 351870928
1 913315720
2 4
1 165426182
1 539661032
3 842094943
3 726768630
1 585756645
1 327182255
3 928037381
3 819034974
3 749190162
3 676969663
2 2
1 802722944
1 848855782
3 227383778
1 725550812
3 892603437
1 451994900
3 470357939
2 1
1 598424975
3 786248...

output:

result:

ok 173 numbers

Test #6:

score: 0

Accepted

time: 0ms

memory: 3652kb

input:

output:

0
1

result:

ok 2 number(s): "0 1"

Test #7:

score: 0

Accepted

time: 222ms

memory: 18912kb

input:

output:

result:

ok 167358 numbers

Test #8:

score: 0

Accepted

time: 634ms

memory: 41148kb

input:

500000
3 1
1 34999032
2 1
3 20479366
3 16132210
3 10950706
3 27656988
3 18181558
3 20096893
1 83795773
3 113805204
3 115628116
1 42488647
1 42211622
2 3
1 92268056
2 2
1 80060142
2 4
1 49696107
3 299966231
3 365132652
1 46139635
1 64375123
2 8
3 39930760
1 14908781
3 210153892
1 85648326
3 568835561...

output:

result:

ok 166515 numbers

Test #9:

score: 0

Accepted

time: 547ms

memory: 40956kb

input:

500000
3 1
3 1
3 1
1 85593529
3 57891556
2 1
3 38559908
1 727251945
1 815334095
1 988926819
3 107155104
1 724052442
3 63908582
2 5
2 4
1 84610655
2 2
3 2423402
3 853118582
1 448879846
2 6
2 3
1 815614446
2 8
1 674635945
2 7
1 46140898
3 820338862
2 10
1 692524546
2 11
1 625079933
1 482471788
3 44351...

output:

result:

ok 166286 numbers

Test #10:

score: 0

Accepted

time: 263ms

memory: 116508kb

input:

500000
1 39567744
1 957918384
1 896336073
1 302217145
1 328404139
1 984894105
1 428308004
1 67268263
1 619517065
1 186724562
1 165376000
1 253795867
1 721330183
1 433623064
1 20169195
1 288503667
1 791272786
1 526657641
1 638212274
1 501209932
1 320898519
1 288747265
1 581193313
1 497930627
1 423401...

output:

result:

ok 0 number(s): ""

Test #11:

score: 0

Accepted

time: 192ms

memory: 105192kb

input:

output:

result:

ok 25227 numbers

Test #12:

score: 0

Accepted

time: 297ms

memory: 59732kb

input:

output:

result:

ok 49640 numbers

Test #13:

score: 0

Accepted

time: 318ms

memory: 59856kb

input:

500000
1 325663181
1 341421661
2 1
2 2
1 798695561
1 789604791
2 3
1 752705846
1 271837520
1 2324300
1 156465725
1 552978643
1 704305136
3 708781692
1 538026101
1 554055497
1 551799143
1 928267539
1 162992249
1 178671365
1 41327601
1 34105375
3 583284520
2 4
1 335357707
2 18
2 13
1 351743555
2 11
1 ...

output:

result:

ok 49895 numbers

Test #14:

score: 0

Accepted

time: 199ms

memory: 59940kb

input:

output:

result:

ok 224721 numbers

Test #15:

score: 0

Accepted

time: 93ms

memory: 4720kb

input:

output:

result:

ok 495045 numbers

Test #16:

score: 0

Accepted

time: 764ms

memory: 50672kb

input:

output:

result:

ok 9965 numbers

Test #17:

score: 0

Accepted

time: 138ms

memory: 6620kb

input:

500000
3 863503832
3 285813354
3 414051174
3 97666985
3 466272422
3 448257369
3 956137762
3 387839447
3 504996933
3 971922171
3 737655581
3 914663293
3 431235168
3 598801556
3 197441204
1 9085
3 18435039
1 28953
3 240290602
3 660593544
3 278294539
3 760061094
3 947453399
3 182070243
3 222738570
3 93...

output:

result:

ok 460003 numbers

Test #18:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

5
1 1000000000
2 1
3 1000000000
1 1000000000
3 1000000000

output:

0
2

result:

ok 2 number(s): "0 2"

Test #19:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

1
3 11451419

output:

result:

ok 1 number(s): "0"

Test #20:

score: 0

Accepted

time: 466ms

memory: 40740kb

input:

500000
1 469
1 27403
1 8011
1 3666
3 431375941
1 5586
1 2876
1 911
1 8549
1 5022
1 11870
1 13676
1 14008
1 7714
1 5558
1 23433
1 5420
1 6330
1 1234
1 21150
1 15806
1 10289
1 638
1 1291
1 5427
1 304
1 7921
1 5709
1 586
1 3002
1 12144
1 5379
1 21367
1 10314
1 15571
1 21493
1 2691
1 7216
1 762
1 7791
1...

output:

result:

ok 20003 numbers

Test #21:

score: 0

Accepted

time: 461ms

memory: 42244kb

input:

output:

24734
167977
249999

result:

ok 3 number(s): "24734 167977 249999"

Test #22:

score: 0

Accepted

time: 426ms

memory: 37764kb

input:

500000
1 471049
3 210537770
3 174642262
3 409419351
1 117066
1 33053
1 13142
3 181598847
1 129357
1 37381
1 197686
3 478570811
1 58776
1 14683
1 151018
3 51491818
1 138638
1 85547
1 188477
1 757
1 3848
1 53283
1 77145
1 29393
1 91077
1 132182
3 167622476
1 110618
1 29202
1 133185
1 33985
3 436250120...

output:

result:

ok 200002 numbers

Test #23:

score: 0

Accepted

time: 563ms

memory: 59140kb

input:

output:

result:

ok 10002 numbers

Test #24:

score: 0

Accepted

time: 226ms

memory: 77408kb

input:

output:

result:

ok 101 numbers

Test #25:

score: 0

Accepted

time: 196ms

memory: 78808kb

input:

output:

result:

ok 6 numbers

Test #26:

score: 0

Accepted

time: 306ms

memory: 52020kb

input:

output:

result:

ok 50000 numbers

Test #27:

score: 0

Accepted

time: 278ms

memory: 44716kb

input:

output:

result:

ok 100000 numbers

Test #28:

score: 0

Accepted

time: 211ms

memory: 44112kb

input:

output:

result:

ok 106787 numbers

Test #29:

score: 0

Accepted

time: 237ms

memory: 54136kb

input:

output:

result:

ok 19985 numbers

Test #30:

score: 0

Accepted

time: 74ms

memory: 3700kb

input:

output:

result:

ok 499516 numbers

Test #31:

score: 0

Accepted

time: 109ms

memory: 6108kb

input:

output:

result:

ok 489886 numbers

Test #32:

score: 0

Accepted

time: 132ms

memory: 9088kb

input:

output:

result:

ok 474862 numbers

Test #33:

score: 0

Accepted

time: 233ms

memory: 116640kb

input:

output:

result:

ok 64 numbers

Test #34:

score: 0

Accepted

time: 45ms

memory: 3812kb

input:

output:

result:

ok 500000 numbers

Test #35:

score: 0

Accepted

time: 61ms

memory: 3536kb

input:

500000
1 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 10000...

output:

result:

ok 499999 numbers

Extra Test:

score: 0

Extra Test Passed