Submission #00361

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define reep(i,a,b) for(int i=a; i<b; i++)
#define MOD 1000000007LL
#define fi first
#define se second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
template <class Tp>
class fenwick_tree{
std::vector<Tp> bit;
public:
fenwick_tree(){}
explicit fenwick_tree(std::size_t n) : bit(n + 1) {}
Tp sum(std::size_t i) const{
i++;
Tp s = 0;
while(i){
s += bit[i];
i -= i & -i;
}
return s;
}
void add(std::size_t i, Tp x){
i++;
while(i < bit.size()){
bit[i] += x;
i += i & -i;
}
}
void clear(){
bit.clear();
}
void assign(std::size_t n){
bit.assign(n + 1, Tp());
}
void swap(fenwick_tree &f){
bit.swap(f.bit);
}
};
int main(){
int n;
cin>>n;
int Q;
cin>>Q;
fenwick_tree<int> bit(1000010);
vint v(n,0);
vector<map<int,int>> ma(1000010);
rep(i,Q){
int a;
cin>>a;
if(a==1){
int b,c;
cin>>b>>c;
c--;
if(v[c] < b){
if(v[c]){
bit.add(v[c]/1000,-1);
ma[v[c]/1000][v[c]%1000]--;
if(ma[v[c]/1000][v[c]%1000]==0){
ma[v[c]/1000].erase(v[c]%1000);
}
}
bit.add(b, 1);
v[c] = b;
ma[v[c]/1000][v[c]%1000]++;
}
}
else{
int b;
cin>>b;
int ans = bit.sum(1000010);
if(b/1000) ans -= bit.sum(b/1000 - 1);
// cout<<"a "<<ans<<endl;
if(b/1000) for(auto x: ma[b/1000-1]){
if(x.fi > b % 1000) continue;
ans += x.se;
}
cout<<ans<<endl;
}
}
}

ステータス

項目 データ
問題 0002 - ghoststudents
ユーザー名 yellow_jam
投稿日時 2017-07-07 22:59:30
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 1628 Byte
最大実行時間 38 ms
最大メモリ使用量 51712 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_01.in AC 26 ms 51296 KB
1
01_small_01.in AC 30 ms 51168 KB
1
01_small_02.in AC 27 ms 51304 KB
1
01_small_03.in AC 28 ms 51312 KB
1
01_small_04.in WA 21 ms 51188 KB
1
01_small_05.in AC 24 ms 51320 KB
1
01_small_06.in AC 24 ms 51320 KB
1
01_small_07.in WA 23 ms 51324 KB
1
01_small_08.in AC 29 ms 51328 KB
1
01_small_09.in WA 24 ms 51332 KB
1
01_small_10.in WA 22 ms 51336 KB
1
02_random_01.in WA 24 ms 51600 KB
1
02_random_02.in WA 28 ms 51492 KB
1
02_random_03.in WA 28 ms 51576 KB
1
02_random_04.in WA 24 ms 51588 KB
1
02_random_05.in WA 31 ms 51396 KB
1
02_random_06.in WA 38 ms 51552 KB
1
02_random_07.in WA 25 ms 51648 KB
1
02_random_08.in WA 28 ms 51544 KB
1
02_random_09.in WA 28 ms 51392 KB
1
02_random_10.in WA 28 ms 51380 KB
1
02_random_11.in WA 31 ms 51608 KB
1
02_random_12.in WA 27 ms 51448 KB
1
02_random_13.in WA 27 ms 51676 KB
1
02_random_14.in WA 34 ms 51564 KB
1
02_random_15.in WA 25 ms 51528 KB
1
02_random_16.in WA 27 ms 51296 KB
1
02_random_17.in WA 26 ms 51496 KB
1
02_random_18.in WA 26 ms 51660 KB
1
02_random_19.in WA 26 ms 51668 KB
1
02_random_20.in WA 25 ms 51360 KB
1
02_random_21.in WA 28 ms 51452 KB
1
02_random_22.in WA 23 ms 51224 KB
1
02_random_23.in WA 24 ms 51320 KB
1
02_random_24.in WA 24 ms 51252 KB
1
02_random_25.in WA 25 ms 51660 KB
1
02_random_26.in WA 30 ms 51400 KB
1
02_random_27.in WA 31 ms 51456 KB
1
02_random_28.in WA 32 ms 51712 KB
1
02_random_29.in WA 25 ms 51392 KB
1
02_random_30.in WA 28 ms 51400 KB
1
03_large_01.in WA 26 ms 51712 KB
1
03_large_02.in WA 27 ms 51580 KB
1
03_large_03.in WA 29 ms 51580 KB
1
03_large_04.in WA 25 ms 51576 KB
1
03_large_05.in WA 25 ms 51580 KB
1
03_large_06.in WA 34 ms 51576 KB
1
03_large_07.in WA 29 ms 51700 KB
1
03_large_08.in WA 29 ms 51564 KB
1
03_large_09.in WA 30 ms 51564 KB
1
03_large_10.in WA 29 ms 51688 KB
1