----------↵
↵
Editorial not found.↵
↵
It will appear here very soon.
↵
[problem:785A]↵
↵
<spoiler summary="Hint">↵
404 Not Found↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:785A]↵
</spoiler>↵
↵
<spoiler summary="C++ code">↵
~~~~~↵
#include <iostream>↵
#include <map>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
map<string, int> vals;↵
vals["Tetrahedron"] = 4;↵
vals["Cube"] = 6;↵
vals["Octahedron"] = 8;↵
vals["Dodecahedron"] = 12;↵
vals["Icosahedron"] = 20;↵
int n; cin >> n;↵
int res = 0;↵
for (int i = 0; i < n; i++) {↵
string s; cin >> s;↵
res += vals[s];↵
}↵
cout << res << endl;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class PolyhedronSums {↵
public static void main(String[] args) throws Exception {↵
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));↵
HashMap<String, Integer> vals = new HashMap<String, Integer>();↵
vals.put("Tetrahedron", 4);↵
vals.put("Cube", 6);↵
vals.put("Octahedron", 8);↵
vals.put("Dodecahedron", 12);↵
vals.put("Icosahedron", 20);↵
int n = Integer.parseInt(reader.readLine());↵
int res = 0;↵
for (int i = 0; i < n; i++) {↵
res += vals.get(reader.readLine());↵
} ↵
writer.write(Integer.toString(res));↵
reader.close();↵
writer.close();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Python code">↵
~~~~~↵
vals = {↵
'Tetrahedron': 4,↵
'Cube': 6,↵
'Octahedron': 8,↵
'Dodecahedron': 12,↵
'Icosahedron': 20↵
}↵
↵
n = int(input())↵
ans = 0↵
for i in range(0, n):↵
ans += vals[input()]↵
print(ans)↵
~~~~~↵
</spoiler>↵
↵
[problem:785B]↵
↵
<spoiler summary="Hint">↵
Think of what periods to take if Anton attends chess classes earlier than programming classes and vice versa.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:785B]↵
</spoiler>↵
↵
<spoiler summary="C++ code">↵
~~~~~↵
#include <iostream>↵
#include <algorithm>↵
↵
const int infinity = 1234567890;↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
int n; cin >> n;↵
vector<pair<int, int> > a(n);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i].first >> a[i].second;↵
}↵
int m; cin >> m;↵
vector<pair<int, int> > b(m);↵
for (int i = 0; i < m; i++) {↵
cin >> b[i].first >> b[i].second;↵
}↵
int minR1 = infinity, maxL1 = -infinity;↵
int minR2 = infinity, maxL2 = -infinity;↵
for (int i = 0; i < n; i++) {↵
maxL1 = max(maxL1, a[i].first);↵
minR1 = min(minR1, a[i].second); ↵
}↵
for (int i = 0; i < m; i++) {↵
maxL2 = max(maxL2, b[i].first);↵
minR2 = min(minR2, b[i].second); ↵
}↵
int res = max(maxL2 - minR1, maxL1 - minR2);↵
cout << max(res, 0) << endl;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class TwoSegments {↵
public static final int infinity = 1234567890;↵
↵
public static class Segment {↵
public int l;↵
public int r;↵
↵
public Segment(int aL, int aR) {↵
l = aL;↵
r = aR;↵
} ↵
}↵
↵
private static Segment[] readList(BufferedReader reader) throws Exception {↵
int n = Integer.parseInt(reader.readLine());↵
Segment[] res = new Segment[n];↵
for (int i = 0; i < n; i++) {↵
StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); ↵
int l = Integer.parseInt(tokenizer.nextToken());↵
int r = Integer.parseInt(tokenizer.nextToken());↵
res[i] = new Segment(l, r);↵
}↵
return res;↵
}↵
↵
public static void main(String[] args) throws Exception {↵
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));↵
Segment[] a = readList(reader);↵
Segment[] b = readList(reader);↵
int minR1 = infinity, maxL1 = -infinity;↵
int minR2 = infinity, maxL2 = -infinity;↵
for (int i = 0; i < a.length; i++) {↵
maxL1 = Math.max(maxL1, a[i].l);↵
minR1 = Math.min(minR1, a[i].r); ↵
}↵
for (int i = 0; i < b.length; i++) {↵
maxL2 = Math.max(maxL2, b[i].l);↵
minR2 = Math.min(minR2, b[i].r); ↵
}↵
int res = Math.max(maxL2 - minR1, maxL1 - minR2);↵
writer.write(Integer.toString(Math.max(res, 0)));↵
reader.close();↵
writer.close();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Python code">↵
~~~~~↵
infinity = 1234567890↵
minR1 = minR2 = infinity↵
maxL1 = maxL2 = -infinity↵
n = int(input())↵
for i in range(0, n):↵
(l, r) = map(int, input().split())↵
maxL1 = max(maxL1, l)↵
minR1 = min(minR1, r)↵
m = int(input())↵
for i in range(0, m):↵
(l, r) = map(int, input().split())↵
maxL2 = max(maxL2, l)↵
minR2 = min(minR2, r)↵
res = max(maxL2 - minR1, maxL1 - minR2);↵
print(max(res, 0))↵
~~~~~↵
</spoiler>↵
↵
[problem:785C]↵
↵
This problem had weak pretests. It was made intentionally to cause more hacks. And I have warned you about it in the announcement :)↵
↵
<spoiler summary="Hint">↵
Model the process to determine how the number of corns in the barn changes.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:785C]↵
</spoiler>↵
↵
<spoiler summary="C++ code">↵
~~~~~↵
#include <iostream>↵
#include <cstdint>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
int64_t n, m;↵
cin >> n >> m;↵
if (n <= m) {↵
cout << n << endl;↵
} else {↵
n -= m;↵
int64_t l = 0, r = 2e9;↵
while (l < r) {↵
int64_t m = (l + r) / 2;↵
int64_t val = m * (m+1) / 2;↵
if (val >= n) {↵
r = m;↵
} else {↵
l = m+1;↵
}↵
}↵
cout << l + m << endl;↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class SparrowsJava {↵
public static void main(String[] args) throws Exception {↵
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));↵
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());↵
long n = Long.parseLong(tokenizer.nextToken());↵
long m = Long.parseLong(tokenizer.nextToken()); ↵
if (n <= m) {↵
writer.write(Long.toString(n));↵
} else {↵
n -= m;↵
long l = 0, r = (long)2e9;↵
while (l < r) {↵
long med = (l + r) / 2;↵
long val = med * (med+1) / 2;↵
if (val >= n) {↵
r = med;↵
} else {↵
l = med+1;↵
}↵
}↵
writer.write(Long.toString(l + m));↵
}↵
reader.close();↵
writer.close();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Python code">↵
~~~~~↵
(n, m) = map(int, input().split())↵
if n <= m:↵
print(n)↵
else:↵
aM = m↵
n -= m↵
(l, r) = (0, int(2e9))↵
while l < r:↵
m = (l + r) // 2;↵
val = m * (m+1) // 2;↵
if val >= n:↵
r = m↵
else:↵
l = m+1↵
print(l + aM)↵
~~~~~↵
</spoiler>↵
↵
[problem:785D]↵
↵
<spoiler summary="Hint">↵
Solve a simplified version of the problem. Let our sequence first contains $x$ opening brackets and then contains $y$ closing brackets, and the last opening bracket must necessarily appear in our RSBS. Use a naive solution to see how the answer looks. Think what to do next.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:785D]↵
</spoiler>↵
↵
<spoiler summary="C++ code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <cstdint>↵
↵
using namespace std;↵
↵
int mod = (int)1e9 + 7;↵
↵
int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { ↵
if (!a) {↵
x = 0;↵
y = 1;↵
return b;↵
}↵
int64_t x1, y1;↵
int64_t d = extGcd(b % a, a, x1, y1);↵
x = y1 - (b / a) * x1;↵
y = x1;↵
return d;↵
}↵
↵
inline int addMod(int a, int b, int m = mod) {↵
return ((int64_t)a + b) % m;↵
}↵
↵
inline int mulMod(int a, int b, int m = mod) {↵
return ((int64_t)a * b) % m;↵
}↵
↵
inline int divMod(int a, int b, int m = mod) {↵
int64_t x, y;↵
int64_t g = extGcd(b, m, x, y);↵
if (g != 1) {↵
cerr << "Bad gcd!" << endl;↵
for (;;);↵
}↵
x = (x % m + m) % m;↵
return mulMod(a, x, m);↵
}↵
↵
const int factRange = 1000000;↵
int fact[factRange];↵
↵
inline void precalcFactorials() {↵
fact[0] = 1;↵
for (int i = 1; i < factRange; i++) {↵
fact[i] = mulMod(fact[i-1], i);↵
}↵
}↵
↵
inline int F(int n) {↵
return (n < 0) ? 0 : fact[n];↵
}↵
↵
inline int C(int k, int n) {↵
return divMod(F(n), mulMod(F(n-k), F(k)));↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
string s; ↵
cin >> s;↵
int len = s.size();↵
precalcFactorials();↵
vector<int> opnLeft(len), clsRight(len);↵
opnLeft[0] = (s[0] == '(') ? 1 : 0;↵
for (int i = 1; i < len; i++) {↵
opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0);↵
}↵
clsRight[len-1] = (s[len-1] == ')') ? 1 : 0;↵
for (int i = len-2; i >= 0; i--) {↵
clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0);↵
}↵
int res = 0;↵
for (int i = 0; i < len; i++) {↵
if (s[i] != '(' || clsRight[i] == 0) {↵
continue;↵
}↵
int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);↵
res = addMod(res, add);↵
}↵
cout << res << endl;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class BracketsJava {↵
public static int mod = (int)1e9 + 7;↵
↵
public static class ExtGcdResult {↵
long x;↵
long y;↵
}↵
↵
public static long extGcd(long a, long b, ExtGcdResult res) { ↵
if (a == 0) {↵
res.x = 0L;↵
res.y = 1L;↵
return b;↵
}↵
ExtGcdResult newRes = new ExtGcdResult();↵
long d = extGcd(b % a, a, newRes); ↵
res.x = newRes.y - (b / a) * newRes.x;↵
res.y = newRes.x;↵
return d; ↵
}↵
↵
public static final int addMod(int a, int b) { ↵
return (int)(((long)a + b) % mod); ↵
}↵
↵
public static final int mulMod(int a, int b) { ↵
return (int)(((long)a * b) % mod); ↵
}↵
↵
public static final int divMod(int a, int b) { ↵
ExtGcdResult res = new ExtGcdResult();↵
long g = extGcd(b, mod, res); ↵
if (g != 1) {↵
System.out.println("Bad gcd!");↵
for (;;);↵
}↵
int q = (int)((res.x % mod + mod) % mod); ↵
return mulMod(a, q); ↵
}↵
↵
public static final int[] precalcFactorials() {↵
int[] fact = new int[factRange];↵
fact[0] = 1;↵
for (int i = 1; i < factRange; i++) {↵
fact[i] = mulMod(fact[i-1], i);↵
}↵
return fact;↵
}↵
↵
public static final int factRange = 1000000;↵
public static final int[] fact = precalcFactorials();↵
↵
public static final int F(int n) {↵
return (n < 0) ? 0 : fact[n];↵
}↵
↵
public static final int C(int k, int n) {↵
int res = divMod(F(n), mulMod(F(n-k), F(k)));↵
return divMod(F(n), mulMod(F(n-k), F(k)));↵
} ↵
↵
public static void main(String[] args) throws Exception {↵
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));↵
String s = reader.readLine();↵
int len = s.length();↵
int[] opnLeft = new int[len], clsRight = new int[len];↵
opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0;↵
for (int i = 1; i < len; i++) {↵
opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0);↵
}↵
clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0;↵
for (int i = len-2; i >= 0; i--) {↵
clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0);↵
}↵
int res = 0;↵
for (int i = 0; i < len; i++) {↵
if (s.charAt(i) != '(' || clsRight[i] == 0) {↵
continue;↵
}↵
int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);↵
res = addMod(res, add);↵
} ↵
writer.write(Integer.toString(res));↵
reader.close();↵
writer.close(); ↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:785E]↵
↵
I'm sorry that this problem was not original. I will try my best to prevent this from happening again.↵
↵
↵
If you have TL or ML in this problem, don't think that the time/memory limits are too strict. The model solution works in 1.2 seconds and consumes 9 MB memory.↵
↵
<spoiler summary="Hint">↵
Divide all the queries in $\sqrt{q}$ blocks. Then divide the positions to the mobile (those ones that will change in this block) and immoblile. Think what to do next.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:785E]↵
</spoiler>↵
↵
<spoiler summary="C++ code">↵
~~~~~↵
// Thanks to netman for the idea for this wonderful solution :)↵
#include <iostream>↵
#include <fstream>↵
#include <vector>↵
#include <cstdint>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
class SQRTDecomposition {↵
private:↵
int n, sz;↵
vector<int> val;↵
vector<int> blocks;↵
public:↵
inline void add(int v, int delta) {↵
val[v] += delta;↵
blocks[v / sz] += delta;↵
}↵
↵
inline int sum(int l, int r) { ↵
if (l < 0) {↵
l = 0;↵
}↵
if (r >= n) {↵
r = n;↵
}↵
r++;↵
int res = 0;↵
int lBlock = (l + sz - 1) / sz, rBlock = r / sz;↵
for (int i = lBlock; i < rBlock; i++) {↵
res += blocks[i];↵
}↵
int lBlockR = lBlock * sz, rBlockR = rBlock * sz;↵
if (lBlockR >= rBlockR) {↵
for (int i = l; i < r; i++) {↵
res += val[i];↵
}↵
} else {↵
for (int i = l; i < lBlockR; i++) {↵
res += val[i];↵
}↵
for (int i = rBlockR; i < r; i++) {↵
res += val[i];↵
}↵
}↵
return res;↵
}↵
↵
inline void clear() {↵
val.assign(val.size(), 0);↵
blocks.assign(blocks.size(), 0);↵
}↵
↵
SQRTDecomposition(int n, int sz)↵
: n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) {↵
}↵
};↵
↵
struct ToProcess {↵
int x, y1, y2, sgn, id;↵
};↵
↵
const int BLOCK_SZ_Q = 256;↵
const int BLOCK_SZ_N = 512;↵
const int MAX_N = 200000;↵
↵
int n, q;↵
vector<ToProcess> sortedL[MAX_N], sortedR[MAX_N];↵
SQRTDecomposition sum(MAX_N, BLOCK_SZ_N);↵
int64_t ans[MAX_N], preAns[MAX_N];↵
pair<int, int> queries[MAX_N];↵
vector<int> goods;↵
int p[MAX_N];↵
bool good[MAX_N];↵
↵
inline void add(int q, int sgn, int id) {↵
if (q-1 >= 0) {↵
sortedL[q-1].push_back({q-1, p[q]+1, n-1, sgn, id});↵
}↵
if (q+1 < n) {↵
sortedR[q+1].push_back({q+1, 0, p[q]-1, sgn, id});↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin >> n >> q;↵
for (int i = 0; i < n; i++) {↵
p[i] = i;↵
}↵
for (int i = 0; i < q; i++) {↵
cin >> queries[i].first >> queries[i].second;↵
queries[i].first--; queries[i].second--;↵
}↵
int64_t cnt = 0;↵
for (int i = 0; i < q; i += BLOCK_SZ_Q) {↵
int iEnd = min(q, i + BLOCK_SZ_Q);↵
for (int j = 0; j < n; j++) {↵
good[j] = false;↵
}↵
for (int j = i; j < iEnd; j++) {↵
good[queries[j].first] = true;↵
good[queries[j].second] = true;↵
}↵
goods.clear();↵
for (int j = 0; j < n; j++) {↵
if (good[j]) {↵
goods.push_back(j);↵
}↵
}↵
int64_t goodCnt = 0;↵
for (int j = 0; j < n; j++) {↵
sortedL[j].clear();↵
sortedR[j].clear();↵
}↵
for (int j = i; j < iEnd; j++) {↵
int a = queries[j].first, b = queries[j].second;↵
if (a == b) {↵
ans[j] += goodCnt;↵
continue;↵
}↵
for (int k = 0; k < (int)goods.size(); k++) {↵
int q = goods[k];↵
if (q == a || q == b) {↵
continue;↵
}↵
if ((p[q] < p[a] && q > a) ||↵
(p[q] > p[a] && q < a)) {↵
goodCnt--;↵
}↵
if ((p[q] < p[b] && q > b) ||↵
(p[q] > p[b] && q < b)) {↵
goodCnt--;↵
}↵
if ((p[q] < p[b] && q > a) ||↵
(p[q] > p[b] && q < a)) {↵
goodCnt++;↵
}↵
if ((p[q] < p[a] && q > b) ||↵
(p[q] > p[a] && q < b)) {↵
goodCnt++;↵
}↵
}↵
if ((a < b && p[a] > p[b]) ||↵
(a > b && p[a] < p[b])) {↵
goodCnt--;↵
} else {↵
goodCnt++;↵
}↵
ans[j] += goodCnt;↵
add(a, -1, j);↵
add(b, -1, j);↵
swap(p[a], p[b]);↵
add(a, +1, j);↵
add(b, +1, j);↵
}↵
sum.clear();↵
for (int j = 0; j < n; j++) {↵
if (!good[j]) {↵
sum.add(p[j], 1);↵
}↵
for (int k = 0; k < (int)sortedL[j].size(); k++) {↵
ToProcess &cur = sortedL[j][k];↵
int64_t res = sum.sum(cur.y1, cur.y2);↵
res *= cur.sgn;↵
preAns[cur.id] += res;↵
}↵
}↵
sum.clear();↵
for (int j = n-1; j >= 0; j--) {↵
if (!good[j]) {↵
sum.add(p[j], 1);↵
}↵
for (int k = 0; k < (int)sortedR[j].size(); k++) {↵
ToProcess &cur = sortedR[j][k];↵
int64_t res = sum.sum(cur.y1, cur.y2);↵
res *= cur.sgn;↵
preAns[cur.id] += res;↵
}↵
}↵
for (int j = i; j < iEnd; j++) {↵
if (j != i) {↵
preAns[j] += preAns[j-1]; ↵
}↵
ans[j] += cnt + preAns[j];↵
}↵
cnt = ans[iEnd - 1];↵
}↵
for (int i = 0; i < q; i++) {↵
cout << ans[i] << "\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class InversionNSqrtNNoVectors {↵
private static final int BLOCK_SZ_Q = 256;↵
private static final int BLOCK_SZ_N = 512;↵
↵
public static class ToProcess {↵
public int x, y1, y2, sgn, id;↵
↵
public void set(int pX, int pY1, int pY2, int pSgn, int pId) {↵
x = pX;↵
y1 = pY1;↵
y2 = pY2;↵
sgn = pSgn;↵
id = pId;↵
}↵
↵
public ToProcess() {↵
}↵
}↵
↵
public static class ToProcessCompareAsc implements Comparator<ToProcess> {↵
@Override↵
public int compare(ToProcess o1, ToProcess o2) {↵
return o1.x - o2.x;↵
}↵
}↵
↵
public static class ToProcessCompareDesc implements Comparator<ToProcess> {↵
@Override↵
public int compare(ToProcess o1, ToProcess o2) {↵
return o2.x - o1.x;↵
}↵
}↵
↵
static int n, q;↵
static int[] p;↵
static ToProcess[] queryL, queryR;↵
static int queryLCnt, queryRCnt;↵
static SQRTDecomposition sum;↵
static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc();↵
static ToProcessCompareDesc descCmp = new ToProcessCompareDesc();↵
↵
public static final void add(int q, int sgn, int id) {↵
if (q-1 >= 0) {↵
queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id);↵
}↵
if (q+1 < n) {↵
queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id);↵
}↵
}↵
↵
public static void main(String[] args) throws Exception {↵
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));↵
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());↵
n = Integer.parseInt(tokenizer.nextToken());↵
q = Integer.parseInt(tokenizer.nextToken());↵
int[] qL = new int[q], qR = new int[q];↵
long[] ans = new long[q], preAns = new long[q];↵
p = new int[n];↵
for (int i = 0; i < n; i++) {↵
p[i] = i;↵
}↵
for (int i = 0; i < q; i++) {↵
tokenizer = new StringTokenizer(reader.readLine());↵
qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1;↵
qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1;↵
}↵
long cnt = 0;↵
boolean[] good = new boolean[n];↵
int[] goods = new int[n];↵
int goodsSize = 0;↵
queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q];↵
for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) {↵
queryL[j] = new ToProcess();↵
queryR[j] = new ToProcess();↵
}↵
SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N);↵
for (int i = 0; i < q; i += BLOCK_SZ_Q) {↵
int iEnd = Math.min(q, i + BLOCK_SZ_Q);↵
Arrays.fill(good, false);↵
for (int j = i; j < iEnd; j++) {↵
good[qL[j]] = true;↵
good[qR[j]] = true;↵
}↵
goodsSize = 0;↵
for (int j = 0; j < n; j++) {↵
if (good[j]) {↵
goods[goodsSize++] = j;↵
}↵
}↵
long goodCnt = 0;↵
queryLCnt = 0;↵
queryRCnt = 0;↵
for (int j = i; j < iEnd; j++) {↵
int a = qL[j], b = qR[j];↵
if (a == b) {↵
ans[j] += goodCnt;↵
continue;↵
}↵
for (int k = 0; k < goodsSize; k++) {↵
int q = goods[k];↵
if (q == a || q == b) {↵
continue;↵
}↵
if ((p[q] < p[a] && q > a) ||↵
(p[q] > p[a] && q < a)) {↵
goodCnt--;↵
}↵
if ((p[q] < p[b] && q > b) ||↵
(p[q] > p[b] && q < b)) {↵
goodCnt--;↵
}↵
if ((p[q] < p[b] && q > a) ||↵
(p[q] > p[b] && q < a)) {↵
goodCnt++;↵
}↵
if ((p[q] < p[a] && q > b) ||↵
(p[q] > p[a] && q < b)) {↵
goodCnt++;↵
}↵
}↵
if ((a < b && p[a] > p[b]) ||↵
(a > b && p[a] < p[b])) {↵
goodCnt--;↵
} else {↵
goodCnt++;↵
}↵
ans[j] += goodCnt;↵
add(a, -1, j);↵
add(b, -1, j);↵
int tmp = p[a];↵
p[a] = p[b];↵
p[b] = tmp;↵
add(a, +1, j);↵
add(b, +1, j);↵
}↵
sum.clear();↵
Arrays.sort(queryL, 0, queryLCnt, ascCmp);↵
int curL = 0;↵
for (int j = 0; j < n; j++) {↵
if (!good[j]) {↵
sum.add(p[j], 1);↵
}↵
for (; curL < queryLCnt; curL++) {↵
ToProcess cur = queryL[curL];↵
if (cur.x != j) {↵
break;↵
}↵
int res = sum.sum(cur.y1, cur.y2);↵
res *= cur.sgn;↵
preAns[cur.id] += res;↵
}↵
}↵
sum.clear();↵
Arrays.sort(queryR, 0, queryRCnt, descCmp);↵
int curR = 0;↵
for (int j = n-1; j >= 0; j--) {↵
if (!good[j]) {↵
sum.add(p[j], 1);↵
}↵
for (; curR < queryRCnt; curR++) {↵
ToProcess cur = queryR[curR];↵
if (cur.x != j) {↵
break;↵
}↵
int res = sum.sum(cur.y1, cur.y2);↵
res *= cur.sgn;↵
preAns[cur.id] += res;↵
}↵
}↵
for (int j = i; j < iEnd; j++) {↵
if (j != i) {↵
preAns[j] += preAns[j-1]; ↵
}↵
ans[j] += cnt + preAns[j];↵
}↵
cnt = ans[iEnd - 1];↵
}↵
for (int i = 0; i < q; i++) {↵
writer.write(Long.toString(ans[i]));↵
writer.newLine();↵
}↵
reader.close();↵
writer.close();↵
}↵
}↵
↵
class SQRTDecomposition {↵
private int n;↵
private int sz;↵
private int[] val;↵
private int[] blocks;↵
↵
public final void add(int v, int delta) {↵
val[v] += delta;↵
blocks[v / sz] += delta;↵
}↵
↵
public final int sum(int l, int r) { ↵
if (l < 0) {↵
l = 0;↵
}↵
if (r >= n) {↵
r = n;↵
}↵
r++;↵
int res = 0;↵
int lBlock = (l + sz - 1) / sz, rBlock = r / sz;↵
for (int i = lBlock; i < rBlock; i++) {↵
res += blocks[i];↵
}↵
int lBlockR = lBlock * sz, rBlockR = rBlock * sz;↵
if (lBlockR >= rBlockR) {↵
for (int i = l; i < r; i++) {↵
res += val[i];↵
}↵
} else {↵
for (int i = l; i < lBlockR; i++) {↵
res += val[i];↵
}↵
for (int i = rBlockR; i < r; i++) {↵
res += val[i];↵
}↵
}↵
return res;↵
}↵
↵
public void clear() {↵
Arrays.fill(val, 0);↵
Arrays.fill(blocks, 0);↵
}↵
↵
SQRTDecomposition(int pN, int pSz) {↵
n = pN;↵
sz = pSz;↵
val = new int[n];↵
blocks = new int[(n + sz - 1) / sz];↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Alternative solution from [user:Vladik,2017-03-15]:↵
↵
<spoiler summary="C++ code">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <cmath>↵
#include <set>↵
#include <map>↵
#include <vector>↵
#include <iomanip>↵
↵
#define sqr(a) (a)*(a)↵
#define all(a) (a).begin(), (a).end()↵
using namespace std;↵
↵
template <typename T>↵
T next_int() {↵
T ans = 0, t = 1;↵
char ch;↵
do { ch = getchar(); } while(ch <= ' ') ;↵
if(ch == '-') {↵
t = -1;↵
ch = getchar();↵
}↵
while(ch >= '0' && ch <= '9') {↵
ans = ans * 10 + (ch - '0');↵
ch = getchar();↵
}↵
return ans * t;↵
}↵
↵
string next_token() {↵
char ch;↵
string ans = "";↵
do { ch = getchar(); } while(ch <= ' ') ;↵
while(ch >= ' ') {↵
ans += ch;↵
ch = getchar();↵
}↵
return ans;↵
}↵
↵
const long long INF = (long long)1e18 + 227 + 1;↵
const int INFINT = (int)1e9 + 227 + 1;↵
const int MAXN = (int)2e5 + 227 + 1;↵
const int MOD = (int)1e9 + 7;↵
const long double EPS = 1e-9;↵
↵
long long bin_pow(long long n, long long k) {↵
if(!k) return 1;↵
long long ans = bin_pow(n, k / 2);↵
ans = ans * ans % MOD;↵
if(k % 2) ans = ans * n % MOD;↵
return ans;↵
}↵
↵
struct tree {↵
int size_block;↵
int len; ↵
↵
tree(int len) : len(len) {↵
size_block = sqrt(len);↵
↵
kek.resize(len / size_block + 1, vector<int>(size_block, 0));↵
↵
pr_block.resize(len / size_block + 1, 0);↵
}↵
↵
vector<int> pr_block;↵
vector<vector<int> > kek;↵
↵
void inc(int pos, int num) {↵
int x = pos / size_block;↵
↵
for(int i = pos % size_block; i < size_block; i++) {↵
kek[x][i] += num;↵
}↵
↵
for(int i = 0; i <= len / size_block; i++)↵
if(i == 0) {↵
pr_block[i] = kek[i][size_block - 1];↵
} else {↵
pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; ↵
}↵
}↵
↵
int f(int a) {↵
return a / size_block;↵
}↵
↵
long long get(vector<int> &a, int l, int r, bool ok = 1) {↵
if(ok == 1) {↵
l %= size_block;↵
r %= size_block;↵
}↵
↵
return a[r] - (l ? a[l - 1] : 0);↵
}↵
↵
int get(int l, int r) {↵
if(l > r) return 0;↵
↵
r = min(r, len);↵
↵
if(f(l) == f(r))↵
return get(kek[f(l)], l, r);↵
↵
int ans = 0;↵
↵
if(l % size_block) {↵
ans += get(kek[f(l)], l, size_block - 1);↵
↵
l += size_block - l % size_block;↵
}↵
↵
if(r % size_block != size_block - 1) {↵
ans += get(kek[f(r)], 0, r);↵
↵
r -= r % size_block + 1;↵
}↵
↵
ans += get(pr_block, f(l), f(r), 0);↵
↵
return ans;↵
}↵
↵
int get_pref(int p) {↵
return get(1, p - 1);↵
}↵
↵
int get_suff(int p) {↵
return get(p + 1, len);↵
}↵
} ;↵
↵
struct mda {↵
vector<int> a;↵
vector<tree> t;↵
int len, sz;↵
long long ans;↵
↵
mda(int len) : len(len) {↵
sz = 2000;↵
ans = 0;↵
↵
a.resize(len + 1);↵
for(int i = 1; i <= len; i++)↵
a[i] = i;↵
↵
for(int i = 1; i <= len; i += sz) {↵
t.push_back(tree(len));↵
for(int j = i; j < i + sz && j <= len; j++)↵
add(j, j);↵
}↵
}↵
↵
int get_pref(int L, int R, int k) {↵
int ans = 0;↵
↵
for(int l = 1; l <= R; l += sz) {↵
int r = l + sz - 1;↵
↵
if(r < L || l > R) continue;↵
↵
if(L <= l && r <= R)↵
ans += t[(l - 1) / sz].get_pref(k);↵
else↵
for(int i = max(l, L); i <= min(r, R); i++) ↵
ans += (a[i] < k);↵
}↵
↵
return ans;↵
}↵
↵
int get_suff(int L, int R, int k) {↵
int ans = 0;↵
↵
for(int l = 1; l <= R; l += sz) {↵
int r = l + sz - 1;↵
↵
if(r < L || l > R) continue;↵
↵
if(L <= l && r <= R)↵
ans += t[(l - 1) / sz].get_suff(k);↵
else↵
for(int i = max(l, L); i <= min(r, R); i++) ↵
ans += (a[i] > k);↵
}↵
↵
return ans;↵
}↵
↵
void del(int p, int k) {↵
p = (p - 1) / sz;↵
t[p].inc(k, -1);↵
}↵
↵
void add(int p, int k) {↵
p = (p - 1) / sz;↵
t[p].inc(k, 1);↵
}↵
↵
void sw(int i, int j) {↵
if(i == j) return;↵
if(i > j) swap(i, j);↵
↵
ans -= get_pref(i, j, a[i]);↵
ans -= get_suff(i, j, a[j]);↵
↵
if(a[i] > a[j]) ans++;↵
↵
del(i, a[i]);↵
del(j, a[j]);↵
swap(a[i], a[j]);↵
add(i, a[i]);↵
add(j, a[j]);↵
↵
ans += get_pref(i, j, a[i]);↵
ans += get_suff(i, j, a[j]);↵
↵
if(a[i] > a[j]) ans--;↵
}↵
} ;↵
↵
int main() {↵
// freopen(".in", "r", stdin);↵
↵
int n, m; cin >> n >> m;↵
↵
mda t(n);↵
↵
for(int i = 0; i < m; i++) {↵
int x, y; cin >> x >> y;↵
↵
t.sw(x, y);↵
↵
cout << t.ans << "\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
Alternative solution from [user:netman,2017-03-15]:↵
↵
<spoiler summary="Java code">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class NsqrtNlogNnetman implements Runnable {↵
static class InputReader {↵
BufferedReader reader;↵
StringTokenizer tokenizer;↵
InputReader(InputStream in) {↵
reader = new BufferedReader(new InputStreamReader(in), 32768);↵
tokenizer = null;↵
}↵
String next() {↵
while (tokenizer == null || !tokenizer.hasMoreTokens()) {↵
try {↵
tokenizer = new StringTokenizer(reader.readLine());↵
} catch (IOException e) {↵
e.printStackTrace();↵
throw new RuntimeException(e);↵
}↵
}↵
return tokenizer.nextToken();↵
}↵
int nextInt() {↵
return Integer.parseInt(next());↵
}↵
long nextLong() {↵
return Long.parseLong(next());↵
}↵
double nextDouble() {↵
return Double.parseDouble(next());↵
}↵
}↵
↵
static class Fenwick {↵
int[] ft;↵
Fenwick(int n) {↵
ft = new int[n];↵
}↵
void add(int r, int val) {↵
while (r < ft.length) {↵
ft[r] += val;↵
r |= r + 1;↵
}↵
}↵
int sum(int r) {↵
int res = 0;↵
while (r >= 0) {↵
res += ft[r];↵
r = (r & (r + 1)) - 1;↵
}↵
return res;↵
}↵
void clear() {↵
Arrays.fill(ft, 0);↵
}↵
}↵
↵
static class Query {↵
int x, bound, sign, id;↵
Query(int x, int bound, int sign, int id) {↵
this.x = x;↵
this.bound = bound;↵
this.sign = sign;↵
this.id = id;↵
}↵
}↵
↵
static void getOnPrefSmaller(List<Query> qrs, int r, int y, int id, int sign) {↵
qrs.add(new Query(r, y, sign, id));↵
}↵
↵
static void getOnPrefBetween(List<Query> qrs, int r, int x, int y, int id, int sign) {↵
getOnPrefSmaller(qrs, r, y, id, sign);↵
getOnPrefSmaller(qrs, r, x, id, -sign);↵
}↵
↵
static void getOnSegmentBetween(List<Query> qrs, int l, int r, int x, int y, int id, int sign) {↵
if (x > y) return;↵
getOnPrefBetween(qrs, r, x, y, id, sign);↵
getOnPrefBetween(qrs, l, x, y, id, -sign);↵
}↵
↵
@Override↵
public void run() {↵
↵
InputReader in = new InputReader(System.in);↵
PrintWriter out = new PrintWriter(System.out);↵
↵
int n = in.nextInt();↵
int q = in.nextInt();↵
↵
int[] l = new int[q];↵
int[] r = new int[q];↵
↵
for (int i = 0; i < q; i++) {↵
l[i] = in.nextInt() - 1;↵
r[i] = in.nextInt() - 1;↵
}↵
↵
int[] perm = new int[n];↵
↵
for (int i = 0; i < n; i++) {↵
perm[i] = n - i - 1;↵
}↵
↵
final int BLOCK = 300;↵
↵
long inv = 0L;↵
↵
boolean[] isInteresting = new boolean[n];↵
↵
long[] add = new long[q];↵
↵
Fenwick f = new Fenwick(n);↵
↵
for (int i = 0; i < q; i += BLOCK) {↵
int from = i, to = Math.min(i + BLOCK, q) - 1;↵
List<Integer> lst = new ArrayList<>();↵
for (int j = from; j <= to; j++) {↵
lst.add(l[j]);↵
lst.add(r[j]);↵
}↵
lst.sort(Integer::compareTo);↵
lst = new ArrayList<>(new HashSet<>(lst));↵
int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray();↵
for (int pos : interestingPositions) {↵
isInteresting[pos] = true;↵
}↵
List<Query> qrs = new ArrayList<>();↵
for (int j = from; j <= to; j++) {↵
if (l[j] == r[j]) continue;↵
if (l[j] > r[j]) {↵
int tmp = l[j];↵
l[j] = r[j];↵
r[j] = tmp;↵
}↵
if (perm[l[j]] < perm[r[j]]) {↵
getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1);↵
int leftValue = perm[l[j]];↵
int rightValue = perm[r[j]];↵
for (int pos : interestingPositions) {↵
if (pos > l[j] && pos < r[j] && perm[pos] > leftValue && perm[pos] < rightValue) {↵
add[j] -= 2;↵
}↵
}↵
add[j]--;↵
} else {↵
getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1);↵
int leftValue = perm[l[j]];↵
int rightValue = perm[r[j]];↵
for (int pos : interestingPositions) {↵
if (pos > l[j] && pos < r[j] && perm[pos] > rightValue && perm[pos] < leftValue) {↵
add[j] += 2;↵
}↵
}↵
add[j]++;↵
}↵
int tmp = perm[l[j]];↵
perm[l[j]] = perm[r[j]];↵
perm[r[j]] = tmp;↵
}↵
qrs.sort(Comparator.comparingInt(a -> -a.x));↵
↵
f.clear();↵
for (int pos = 0; pos < n; pos++) {↵
if (!isInteresting[pos]) {↵
f.add(perm[pos], 1);↵
}↵
while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) {↵
Query t = qrs.get(qrs.size() - 1);↵
qrs.remove(qrs.size() - 1);↵
add[t.id] += 2 * t.sign * f.sum(t.bound);↵
}↵
}↵
for (int j = from; j <= to; j++) {↵
inv += add[j];↵
out.println(inv);↵
}↵
for (int pos : interestingPositions) {↵
isInteresting[pos] = false;↵
}↵
}↵
↵
↵
↵
out.close();↵
}↵
↵
public static void main(String[] args) {↵
new Thread(null, new NsqrtNlogNnetman(), "1", 1L << 28).run();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
