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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<double> st[(int)1e3+9];
ll n,m,id[(int)1e5+9],fk,l[(int)1e5+9],r[(int)1e5+9];
double a[(int)1e5+9];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
fk=sqrt(n*log(n)/2);
for(int i=1;i<=n;++i){
id[i]=(i-1)/fk+1;
if(!l[id[i]])l[id[i]]=i;
r[id[i]]=i;
}
for(int i=1,x,y;i<=m;++i){
cin>>x>>y;
auto &it=st[id[x]];
a[x]=1.0*y/(x*1.0);
it.clear();
for(int j=l[id[x]];j<=r[id[x]];++j){
if(a[j]==0.0)continue;
if(it.empty()||it.back()<a[j])it.push_back(a[j]);
}
ll ans=0;
double mx=0.0;
for(int j=1;j<=id[n];++j){
auto &aa=st[j];
if(!aa.empty()){
ans+=aa.end()-upper_bound(aa.begin(),aa.end(),mx);
mx=max(mx,aa.back());
}
}
cout<<ans<<"\n";
}
}
|