結果
問題 | No.3011 あ、俺こいつの役やりたい! |
ユーザー |
![]() |
提出日時 | 2025-01-25 16:14:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,931 bytes |
コンパイル時間 | 5,705 ms |
コンパイル使用メモリ | 332,504 KB |
実行使用メモリ | 42,036 KB |
平均クエリ数 | 0.32 |
最終ジャッジ日時 | 2025-01-25 23:52:14 |
合計ジャッジ時間 | 98,593 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 WA * 2 TLE * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll=long long;#define rep1(i,a) for(int i=0;i<(a);i++)#define rep2(i,a,b) for(int i=(a);i<(b);i++)#define rep3(i,a,b,c) for(int i=(a);i<(b);i+=(c))#define overload3(a,b,c,d,e,...) e#define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)#define all(x) (x).begin(),(x).end()#define chmax(x,y)((x)=max(x,y))#define chmin(x,y)((x)=min(x,y))template<class T> vector<T> compress(vector<T> x){vector<T> xs=x;sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end());rep(i,x.size()) x[i]=lower_bound(xs.begin(),xs.end(),x[i])-xs.begin();return x;}template<class T> vector<T> dijkstra(int start,vector<vector<pair<T,int>>> &graph){int n=graph.size();vector<T> dist(n,numeric_limits<T>::max());dist[start]=0;priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> pq;pq.push({0,start});while(!pq.empty()){auto [d,v]=pq.top();pq.pop();if (dist[v]<d)continue;for (auto [nd,nv]:graph[v]){if (dist[nv]>d+nd){dist[nv]=d+nd;pq.push({dist[nv],nv});}}}return dist;}template<class T> struct BIT{vector<T> dat;BIT(int n):dat(n+1,0){}void add(int i,T x){for(++i;i<dat.size();i+=i&-i)dat[i]+=x;}T sum(int i){T res=0;for(++i;i;i-=i&-i)res+=dat[i];return res;}T sum(int l,int r){return sum(r-1)-sum(l-1);}};template<class T> struct MergeSortTree{int n,log,size;vector<vector<T>> dat,sum;T min_elem,max_elem;MergeSortTree(vector<T> a):n(a.size()){min_elem=*min_element(all(a));max_elem=*max_element(all(a));log=0;while ((1LL<<log)<n)log++;size=1<<log;dat.resize(size*2);sum.resize(size*2);for (int i=0;i<n;i++){dat[size+i]={a[i]};sum[size+i]={0,a[i]};}for (int i=size-1;i>0;i--){dat[i]=merge(dat[i*2],dat[i*2+1]);sum[i].resize(dat[i].size()+1,0);for (int j=1;j<sum[i].size();j++)sum[i][j]=sum[i][j-1]+dat[i][j-1];}}vector<T> merge(vector<T> &l, vector<T> &r){vector<T> res;int i=0,j=0;while (i<l.size() && j<r.size()){if (l[i]<r[j])res.push_back(l[i++]);else res.push_back(r[j++]);}while (i<l.size())res.push_back(l[i++]);while (j<r.size())res.push_back(r[j++]);return res;}T range_sum(int l,int r,int x){l+=size;r+=size;T res=0;while (l<r){if (l&1){if (!dat[l].empty())res+=sum[l][upper_bound(dat[l].begin(),dat[l].end(),x)-dat[l].begin()];l++;}if (r&1){r--;if (!dat[r].empty())res+=sum[r][upper_bound(dat[r].begin(),dat[r].end(),x)-dat[r].begin()];}l>>=1;r>>=1;}return res;}int range_freq(int l,int r,int x){l+=size;r+=size;int res=0;while (l<r){if (l&1){if (!dat[l].empty())res+=upper_bound(dat[l].begin(),dat[l].end(),x)-dat[l].begin();l++;}if (r&1){r--;if (!dat[r].empty())res+=upper_bound(dat[r].begin(),dat[r].end(),x)-dat[r].begin();}l>>=1;r>>=1;}return res;}T range_sum(int l,int r,int x,int y){return range_sum(l,r,y-1)-range_sum(l,r,x-1);}int range_freq(int l,int r,int x,int y){return range_freq(l,r,y-1)-range_freq(l,r,x-1);}T get(int k){return (dat[size+k].size() ? dat[size+k][0] : T());}T kth_smallest(int l,int r,int k){T ng=min_elem-1,ok=max_elem+1;while (ok-ng>1){int mid=(ok+ng)/2;if (range_freq(l,r,mid)>k)ok=mid;else ng=mid;}return ok;}T kth_largest(int l,int r,int k){return kth_smallest(l,r,r-l-k-1);}};template<typename S> struct SplayTree{private://using S=long long;static S op(S a, S b) {return a + b;}static S e() {return 0;}using F = long long;static S mapping(F f, S x) {return f + x;}static F composition(F f, F g) {return f + g;}static F id() {return 0;}struct node{S v, prod;F lazy;int cnt, rev;node *l, *r;node(S v): v(v), prod(v), lazy(id()), cnt(1), rev(0){l = r = nullptr;}};node *root=nullptr;int count(node *x){return !x ? 0:x->cnt;}S sum(node *x){return !x ? e():x->prod;}node *rotate(node *x,bool right){node *y= right ? x->l : x->r;all_push(x);all_push(y);if (!y)return x;if (right){x->l=y->r;y->r=x;}else{x->r=y->l;y->l=x;}update(x);update(y);return y;}node *splay(node *x,int k){if (!x)return nullptr;all_push(x);if (k<count(x->l)){if (x->l==nullptr)return x;if (k<count(x->l->l)){x->l->l=splay(x->l->l,k);x=rotate(x,true);}else if (count(x->l->l)<k){x->l->r=splay(x->l->r,k-count(x->l->l)-1);if (x->l->r)x->l=rotate(x->l,false);}return x->l ? rotate(x,true) : update(x);}else if (count(x->l)<k){if (x->r==nullptr)return x;k=k-count(x->l)-1;if (k<count(x->r->l)){x->r->l=splay(x->r->l,k);if (x->r->l)x->r=rotate(x->r,true);}else if (count(x->r->l)<k){x->r->r=splay(x->r->r,k-count(x->r->l)-1);x=rotate(x,false);}return x->r ? rotate(x,false) : update(x);}return update(x);}node *merge(node *l,node *r) {if (!l || !r) return !l ? r : l;r=splay(r,0);r->l=l;return update(r);}pair<node*, node*> split(node *x, int k) {assert(0<=k && k<=size());if (!x) return {nullptr, nullptr};if (k==size())return {x,nullptr};x=splay(x, k);all_push(x);node* l=x->l;x->l=nullptr;return {l,update(x)};}void insert(node *&x,int k,S v) {assert(0<=k && k<=size());auto [l,r]=split(root,k);root=merge(merge(l,new node(v)),r);}void erase(node *&x,int k) {assert(0<=k && k<size());auto [left_mid,right]=split(x,k+1);auto [left,mid]=split(left_mid,k);delete mid;x=merge(left,right);}void erase(node *&x,int l,int r){assert(0<=l && r<=size() && l<=r);x=splay(x,l);auto [left,mid,right]=split3(x,l,r);all_push(x);delete mid;root=merge(left,right);}S get(node *&x,int k){assert(0<=k && k<size());if (!root)return e();x=splay(x,k);all_push(x);update(x);return x->v;}void set(node *&x,int k,S v){assert(0<=k && k<size());x=splay(x,k);x->v=v;}S prod(node *&x,int l,int r) {assert(0<=l && r<=size() && l<=r);x=splay(x,l);auto [left,mid,right]=split3(x,l,r);all_push(mid);S res=sum(update(mid));x=merge(merge(left,mid),right);return res;}void apply(node *&x,int l,int r,F f){assert(0<=l && r<=size() && l<=r);x=splay(x,l);auto [left,mid,right]=split3(x,l,r);if (mid)mid->lazy=composition(f,mid->lazy);x=merge(merge(left,mid),right);}void reverse(node *&x,int l,int r){assert(0<=l && r<=size() && l<=r);auto [left,mid,right]=split3(x,l,r);if (mid)mid->rev=1;x=merge(merge(left,mid),right);}void push(node *x){if (!x)return;if (x->lazy!=id()){x->v=mapping(x->lazy,x->v);x->prod=mapping(x->lazy,x->prod);if (x->l)x->l->lazy=composition(x->lazy,x->l->lazy);if (x->r)x->r->lazy=composition(x->lazy,x->r->lazy);x->lazy=id();}if (x->rev){swap(x->l,x->r);if (x->l)x->l->rev^=1;if (x->r)x->r->rev^=1;x->rev=0;}}void all_push(node *x){push(x);if (x)push(x->l),push(x->r);}node *update(node *x){if (!x)return x;x->cnt=count(x->l)+count(x->r)+1;x->prod=op(op(sum(x->l),x->v),sum(x->r));return x;}tuple<node*, node*, node*> split3(node *x,int l,int r){auto [left_mid,right]=split(x,r);auto [left,mid]=split(left_mid,l);return {left,mid,right};}int bisect_left(node *x,S v){all_push(x);if (!x)return 0;if (v<=x->v)return bisect_left(x->l,v);return count(x->l)+1+bisect_left(x->r,v);}int bisect_right(node *x,S v){all_push(x);if (!x)return 0;if (v<x->v)return bisect_right(x->l,v);return count(x->l)+1+bisect_right(x->r,v);}node *make_tree(vector<S> &v,int l,int r){if (r-l==0)return nullptr;int m=l+(r-l)/2;node *left=make_tree(v,l,m), *right=make_tree(v,m+1,r);node *x=new node(v[m]);x->l=left;x->r=right;return update(x);}public:SplayTree(){}SplayTree(vector<S> v){ root=make_tree(v, 0, v.size()); }int size(){return (!root ? 0 : root->cnt);}void insert_at(int k, S v){ insert(root, k, v); }void insert(S v){ insert(bisect_left(v), v);}void erase_at(int k){ erase(root, k); }void erase(S v){ erase_at(bisect_left(v)); }int count(S v){ return bisect_right(v)-bisect_left(v); }S get(int k){ return get(root, k); }void set(int k, S v){ set(root, k, v); }S prod(int l, int r){ return prod(root, l, r); }void apply(int l, int r, F f){ apply(root, l, r, f); }int bisect_left(S v){ root=splay(root, size()); return bisect_left(root, v); }int bisect_right(S v){ root=splay(root, size()); return bisect_right(root, v); }S lower_bound(S v){ return get(bisect_left(v)); }S upper_bound(S v){ return get(bisect_right(v)); }void reverse(int l, int r){ reverse(root, l, r); }};int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int ng=-1,ok=1e9;while (ok-ng>1){int mid=(ok+ng)/2;cout << mid << endl;int r;cin >> r;if (r==1)return 0;}cout << ok << endl;}