提出 #47695642
ソースコード 拡げる
// Author: XZC(L_Wave)
// Language: Cpp/G++14
// Problem: F - Colored Ball
// Contest: AtCoder - Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 329)
// URL: https://atcoder.jp/contests/abc329/tasks/abc329_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// Create Time: not 2023-11-18 20:00:34, but 1926-08-17 11:45:14
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
int ls[10000010],rs[10000010],cnt[10000010],rt[200010],n,q,tot;
void ins(int&p,int l,int r,int x){
if(!p)p=++tot;
if(l==r){
cnt[p]=1;
return ;
}
int mid=(l+r)>>1;
if(x<=mid)ins(ls[p],l,mid,x);
else ins(rs[p],mid+1,r,x);
cnt[p]=cnt[ls[p]]+cnt[rs[p]];
}
int mg(int p,int q,int l,int r){
if(!p||!q)return p|q;
if(l==r){
cnt[p]=1;
return p;
}
int mid=(l+r)>>1;
ls[p]=mg(ls[p],ls[q],l,mid);
rs[p]=mg(rs[p],rs[q],mid+1,r);
cnt[p]=cnt[ls[p]]+cnt[rs[p]];
return p;
}
int main() {
scanf("%d%d",&n,&q);
rep(i,1,n){
int x;scanf("%d",&x);
ins(rt[i],1,n,x);
}
while(q--){
int x,y;scanf("%d%d",&x,&y);swap(x,y);
rt[x]=mg(rt[x],rt[y],1,n);
rt[y]=0;
printf("%d\n",cnt[rt[x]]);
}
return 0;
}
提出情報
| 提出日時 |
|
| 問題 |
F - Colored Ball |
| ユーザ |
fft_ntt |
| 言語 |
C++ 20 (gcc 12.2) |
| 得点 |
500 |
| コード長 |
1448 Byte |
| 結果 |
AC |
| 実行時間 |
329 ms |
| メモリ |
48900 KiB |
コンパイルエラー
Main.cpp: In function ‘int main()’:
Main.cpp:43:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
43 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:45:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
45 | int x;scanf("%d",&x);
| ~~~~~^~~~~~~~~
Main.cpp:49:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
49 | int x,y;scanf("%d%d",&x,&y);swap(x,y);
| ~~~~~^~~~~~~~~~~~~~
ジャッジ結果
| セット名 |
Sample |
All |
| 得点 / 配点 |
0 / 0 |
500 / 500 |
| 結果 |
|
|
| セット名 |
テストケース |
| Sample |
sample00.txt, sample01.txt |
| All |
sample00.txt, sample01.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt |
| ケース名 |
結果 |
実行時間 |
メモリ |
| sample00.txt |
AC |
1 ms |
3688 KiB |
| sample01.txt |
AC |
1 ms |
3764 KiB |
| testcase00.txt |
AC |
122 ms |
48172 KiB |
| testcase01.txt |
AC |
122 ms |
48172 KiB |
| testcase02.txt |
AC |
244 ms |
48244 KiB |
| testcase03.txt |
AC |
248 ms |
48344 KiB |
| testcase04.txt |
AC |
226 ms |
48232 KiB |
| testcase05.txt |
AC |
231 ms |
48232 KiB |
| testcase06.txt |
AC |
244 ms |
48208 KiB |
| testcase07.txt |
AC |
252 ms |
48228 KiB |
| testcase08.txt |
AC |
226 ms |
48348 KiB |
| testcase09.txt |
AC |
239 ms |
48344 KiB |
| testcase10.txt |
AC |
242 ms |
48220 KiB |
| testcase11.txt |
AC |
245 ms |
48280 KiB |
| testcase12.txt |
AC |
145 ms |
46532 KiB |
| testcase13.txt |
AC |
145 ms |
48900 KiB |
| testcase14.txt |
AC |
125 ms |
44772 KiB |
| testcase15.txt |
AC |
137 ms |
48476 KiB |
| testcase16.txt |
AC |
127 ms |
46552 KiB |
| testcase17.txt |
AC |
136 ms |
48440 KiB |
| testcase18.txt |
AC |
126 ms |
45312 KiB |
| testcase19.txt |
AC |
136 ms |
48044 KiB |
| testcase20.txt |
AC |
134 ms |
48352 KiB |
| testcase21.txt |
AC |
137 ms |
48308 KiB |
| testcase22.txt |
AC |
142 ms |
48152 KiB |
| testcase23.txt |
AC |
142 ms |
48324 KiB |
| testcase24.txt |
AC |
142 ms |
47732 KiB |
| testcase25.txt |
AC |
145 ms |
48364 KiB |
| testcase26.txt |
AC |
134 ms |
45908 KiB |
| testcase27.txt |
AC |
145 ms |
48220 KiB |
| testcase28.txt |
AC |
129 ms |
44236 KiB |
| testcase29.txt |
AC |
144 ms |
48216 KiB |
| testcase30.txt |
AC |
134 ms |
44312 KiB |
| testcase31.txt |
AC |
146 ms |
48356 KiB |
| testcase32.txt |
AC |
144 ms |
47416 KiB |
| testcase33.txt |
AC |
145 ms |
48404 KiB |
| testcase34.txt |
AC |
134 ms |
44968 KiB |
| testcase35.txt |
AC |
144 ms |
48268 KiB |
| testcase36.txt |
AC |
140 ms |
46968 KiB |
| testcase37.txt |
AC |
144 ms |
48192 KiB |
| testcase38.txt |
AC |
131 ms |
43932 KiB |
| testcase39.txt |
AC |
146 ms |
48356 KiB |
| testcase40.txt |
AC |
328 ms |
48248 KiB |
| testcase41.txt |
AC |
329 ms |
48184 KiB |