| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230232 | vako_p | 서열 (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
const int mxN = 1e6 + 5;
ll n,p[mxN],a[mxN],q,mod = 1e9 + 7;
//bool f(ll idx){
// ll curr = 0;
// for(int i = (idx + 1) % n; i != idx; i = (i + 1) % n){
// curr += a[i];
// if(!curr) return false;
// curr--;
// }
// return true;
//}
struct segtree{
vector<ll> v,v1;
ll sz = 1;
void init(){
while(sz < n) sz *= 2;
v.assign(2 * sz, 0LL);
v1.assign(2 * sz, 0LL);
}
void f(ll x){
v[x] += v1[x];
if(x < sz - 1){
v1[2 * x + 1] += v1[x];
v1[2 * x + 2] += v1[x];
}
v1[x] = 0;
}
void set(ll val, ll l, ll r, ll x, ll lx, ll rx){
f(x);
if(lx >= r or rx <= l) return;
if(lx >= l and rx <= r){
v1[x] += val;
f(x);
return;
}
ll mid = lx + (rx - lx) / 2;
set(val, l, r, 2 * x + 1, lx, mid);
set(val, l, r, 2 * x + 2, mid, rx);
v[x] = min(v[2 * x + 1], v[2 * x + 2]);
}
void set(ll val, ll l, ll r){
set(val, l, r, 0, 0, sz);
}
ll find(ll x, ll lx, ll rx){
f(x);
if(rx - lx == 1) return lx;
f(2 * x + 1);
f(2 * x + 2);
ll mid = lx + (rx - lx) / 2;
if(v[2 * x + 1] <= v[2 * x + 2]) return find(2 * x + 1, lx, mid);
return find(2 * x + 2, mid, rx);
}
ll find(){
return find(0, 0, sz);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
ll sum = 0;
segtree s;
s.init();
for(int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
s.set(a[i] - 1, i, n);
}
if(sum != n - 1){
q++;
while(q--) cout << "0 0 \n";
return 0;
}
ll mn = 1e9,idx = 0;
for(int i = 0; i < n; i++){
p[i] = a[i] - 1;
if(i) p[i] += p[i - 1];
if(mn > p[i]){
mn = p[i];
idx = i;
}
}
cout << 1 << " " << (s.find() + 1) % n << '\n';
while(q--){
ll x,y;
cin >> x >> y;
s.set(a[y] - a[x], x, n);
s.set(a[x] - a[y], y, n);
swap(a[x], a[y]);
cout << 1 << " " << (s.find() + 1) % n << '\n';
}
}