| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 141270 | ngot23 | Bubble Sort 2 (JOI18_bubblesort2) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b)-1 ; ++i)
#define mp make_pair
#define pii pair<int, int>
#define PB push_back
#define F first
#define S second
#define Task ""
using namespace std;
template <typename T > inline void MIN(T &a, T b) { if(a>b) a=b; }
template <typename T > inline void MAX(T &a, T b) { if(a<b) a=b; }
const int N=8005;
int n, Q, t[N], L;
vector <int > v, ans, a, id, val;
int get(int id) {
int ret=0;
while(id<=L) {
ret+=t[id];
id+=id&(-id);
}
return ret;
}
void update(int id) {
while(id) {
++t[id];
id-=id&(-id);
}
}
vector <int > countScans(vector <int > a, vector <int > id, vector <int > val) {
vector <int > ret(Q, 0);
rep(j, 0, Q) {
a[id[j]]=val[j];
v.clear();
v.resize(n, 0);
rep(i, 0, n) v[i]=a[i];
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end())-v.begin());
L=v.size();
rep(i, 1, L+1) t[i]=0;
int mx=0;
rep(i, 0, n) {
int r=upper_bound(v.begin(), v.end(), a[i])-v.begin();
MAX(mx, get(r+1));
update(r);
}
ret[j]=mx;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(Task".inp", "r", stdin);
//freopen(Task".out", "w", stdout);
cin >> n >> Q;
a.resize(n);
id.resize(n);
val.resize(n);
rep(i, 0, n) cin >> a[i];
rep(i, 0, Q) cin >> id[i] >> val[i];
ans=countScans(a, id, val);
for(int xx:ans) cout << xx << '\n';
return 0;
}