結果

問題 No.3011 あ、俺こいつの役やりたい!
ユーザー るこーそーるこーそー
提出日時 2025-01-25 16:17:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 10,956 bytes
コンパイル時間 5,349 ms
コンパイル使用メモリ 332,036 KB
実行使用メモリ 25,984 KB
平均クエリ数 20.77
最終ジャッジ日時 2025-01-25 23:51:06
合計ジャッジ時間 12,493 ms
ジャッジサーバーID
(参考情報)
judge4 / judge7
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 12 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 || r==-1)return 0;
ng=mid;
}
cout << ok << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0