Submission #00118

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#define lol long long
#define gcd(x, y) __gcd(x, y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed(x) fixed << setprecision(x)
#define all(x) x.begin(),x.end()
using namespace std;
using pii = pair<int, int>;
template <class A, class B>
inline bool chmax(A& a, const B& b) {
return b > a && (a = b, true);
}
template <class A, class B>
inline bool chmin(A& a, const B& b) {
return b < a && (a = b, true);
}
template <class A>
inline A abs(A& a) {
return (a < 0 ? -a : a);
}
bool inLine(int x, int y, int mx, int my) {
return (x >= 0 && y >= 0 && x < mx && y < my);
}
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<class T> using uset=unordered_set<T>;
template<class A,class B> using umap=unordered_map<A,B>;
const lol inf = (1LL << 62);
const int MOD = (1e9) + 7;
const int mod = 998244353;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1, -2, -2, -2, -2,
-2, -1, -1, 1, 1, 0, 0, 2, 2, 2, 2, 2};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1, -2, -1, 0, 1,
2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2};
template <typename X>
struct Segment{
using FX=function<X(X,X)>; //X●X -> X となる関数の型
int n;
FX fx;
const X ex;
vector<X> dat;
Segment(int size,FX fx_,X ex_) : fx(fx_),ex(ex_){
n=1;
while(size>n){
n*=2;
}
dat.resize(n*2,ex_);
return;
}
void set(int i,X x){ dat[i+n-1]=x;}
void build(){
for(int k=n-2;k>=0;k--) dat[k]=fx(dat[2*k+1],dat[2*k+2]);
return;
}
void update(int i,X x){
i+=n-1;
dat[i]=x;
while(i>0){
i=(i-1)/2;
dat[i]=fx(dat[i*2+1],dat[i*2+2]);
}
return;
}
X get(int a,int b){ return (get_sub(a,b+1,0,0,n));}
X get_sub(int a,int b,int k,int l,int r){
if(r<=a || b<=l) return ex;
if(a<=l && r<=b) return dat[k];
X vl=get_sub(a,b,k*2+1,l,(l+r)/2);
X vr=get_sub(a,b,k*2+2,(l+r)/2,r);
return fx(vl,vr);
}
X operator[](const int &k) const{
return dat[k+n-1];
}
};
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n,q;
cin >>n>>q;
vector<stack<int>> s(n);
Segment<int> st(n+1,[](int x1,int x2) -> int {return x1+x2;},0);
int p=1;
while(q--){
int t,k,c;
cin >>t;
if(t==2){
if(!s[p].empty()){
cout <<s[p].top()<<'\n';
s[p].pop();
if(s[p].empty()){
st.update(p,0);
}
p++;
if(p==n){
p=0;
}
continue;
}
int high=n-1,low=p;
while(high-low>1){
int mid=(high+low)/2;
lol tmp=st.get(low,mid);
if(tmp>0){
high=mid;
}else{
low=mid;
}
}
p=high;
if(s[p].empty()){
if(!s[0].empty()){
p=0;
}else{
high=n-1,low=0;
while(high-low>1){
int mid=(high+low)/2;
lol tmp=st.get(low,mid);
if(tmp>0){
high=mid;
}else{
low=mid;
}
}
p=high;
}
}
if(!s[p].empty()){
cout <<s[p].top()<<'\n';
s[p].pop();
}else{
cout <<"エラー\n";
}
if(s[p].empty()){
st.update(p,0);
}
p++;
if(p==n){
p=0;
}
}else if(t==1){
cin >>k>>c;
k--;
st.update(k,1);
s[k].push(c);
}
}
return (0);
}

ステータス

項目 データ
問題 0005 - Stacking Books
ユーザー名 ei1923
投稿日時 2021-04-07 14:17:58
言語 C++17
状態 Runtime Error
得点 0
ソースコード長 3628 Byte
最大実行時間 661 ms
最大メモリ使用量 159640 KB

セット

セット 得点 Cases
1 ALL 0 / 22 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 245 ms 70108 KB
1
in02.txt AC 273 ms 111512 KB
1
in03.txt AC 198 ms 52420 KB
1
in04.txt AC 202 ms 93200 KB
1
in05.txt AC 266 ms 134476 KB
1
in06.txt AC 469 ms 140036 KB
1
in07.txt AC 467 ms 141020 KB
1
in08.txt AC 463 ms 142136 KB
1
in09.txt AC 528 ms 142996 KB
1
in10.txt AC 448 ms 143988 KB
1
in11.txt AC 492 ms 144976 KB
1
in12.txt AC 473 ms 145964 KB
1
in13.txt AC 513 ms 146956 KB
1
in14.txt AC 481 ms 147948 KB
1
in15.txt AC 496 ms 148936 KB
1
in16.txt AC 661 ms 149924 KB
1
in17.txt AC 620 ms 150780 KB
1
in18.txt AC 637 ms 151768 KB
1
in19.txt AC 414 ms 152632 KB
1
in20.txt AC 661 ms 153108 KB
1
in21.txt AC 468 ms 153588 KB
1
in22.txt AC 163 ms 153548 KB
1
in23.txt AC 147 ms 154404 KB
1
in24.txt AC 135 ms 154444 KB
1
in25.txt AC 40 ms 18156 KB
1
in26.txt AC 56 ms 19128 KB
1
in27.txt AC 46 ms 20092 KB
1
in28.txt AC 49 ms 20932 KB
1
in29.txt AC 30 ms 36236 KB
1
in30.txt AC 24 ms 20968 KB
1
in31.txt AC 348 ms 158392 KB
1
in32.txt RE 86 ms 22296 KB
1
in33.txt AC 604 ms 159640 KB
1
in34.txt AC 135 ms 159236 KB
1
sample01.txt AC 22 ms 22752 KB
1
sample02.txt AC 23 ms 22836 KB
1