---
# System prepended metadata

title: Разбор задач 2011 года

---

# Разбор задач 2011 года
Если Вы не знали как решать какую-то задачу и вам было лень разбираться в коде на Pascal, то это пост специально для Вас.
:::warning
Убедительная просьба не копировать коды и не пересылать их. Помните -- Вы решаете задачи для себя!
:::

## [1. Пересечения](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2011_1)
:::spoiler Разбор
:::info
Для того, чтобы получить 10 баллов, достаточно было заифать претесты. 

__Основная идея__:

Давайте хранить количество линий, которые проходят над $x$-й координатой.

На $30$ баллов можно было обновлять количество линий за $N * (R_i - L_i - 1)$

На $100$ баллов я написал дерево отрезков (асимптотика: $O(N*log(N))$), в авторском решении используется Sqrt-декомпозиция (асимптотика: $O(N * \sqrt{N})$).

*P.S*:
Не забудьте, что _пересечения нескольких фигур в одной точке считается как одно пересечение_.

:::
:::spoiler Авторское решение (Pascal)
```pascal
var
 N, L,R,i,x,sum:longint;
 A:array[1..100000] of longint;
 B:array[0..1000] of longint;
 fo,fi:text;
begin
  readln(N);
  sum:=0;
  for i:=1 to N do begin
    readln(L,R);
    sum:=sum+A[L]+B[L div 256]+A[R]+B[R div 256];
    A[L]:=-B[L div 256];
    A[R]:=-B[R div 256];
    x:=L+1;
    while (x < R) and (x mod 256 <> 0) do begin
      A[x]:=A[x]+1;
      x:=x+1;
    end;
    while x+256 <= R do begin
      B[x div 256]:=B[x div 256]+1;
      x:=x+256;
    end;
    while (x < R) do begin
      A[x]:=A[x]+1;
      x:=x+1;
    end;
  end;
  writeln(sum);
end.
```
:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))
```cpp
#include <bits/stdc++.h>
using namespace std;

vector<int> t;
vector<int> lazy;

int md(int l, int r) {
    return l + (r - l) / 2;
}

void push(int v, int vl, int vr) {
    if (lazy[v] != 0) {
        int mid = md(vl, vr);
        t[2 * v + 1] += lazy[v] * (mid - vl + 1);
        t[2 * v + 2] += lazy[v] * (vr - mid);
        lazy[2 * v + 1] += lazy[v];
        lazy[2 * v + 2] += lazy[v];
        lazy[v] = 0;
    }
}

void upd(int v, int vl, int vr, int l, int r, int val) {
    if (vl > r || vr < l) return;
    if (vl >= l && vr <= r){
        t[v] += (vr - vl + 1) * val;
        lazy[v] += val;
        return;
    }
    push(v, vl, vr);
    int mid = md(vl, vr);
    upd(2 * v + 1, vl, mid, l, r, val);
    upd(2 * v + 2, mid + 1, vr, l, r, val);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
}

int get_(int v, int vl, int vr, int l, int r) {
    if (vl > r || vr < l) return 0;
    if (vl >= l && vr <= r) return t[v];
    push(v, vl, vr);
    int mid = md(vl, vr);
    int q1 = get_(2 * v + 1, vl, mid, l, r);
    int q2 = get_(2 * v + 2, mid + 1, vr, l, r);
    return q1 + q2;
}

int main() {
    int n;
    cin >> n;
    t.resize(4 * N);
    lazy.resize(4 * N);
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        ans += get_(0, 1, N, l, l);
        ans += get_(0, 1, N, r, r);
        upd(0, 1, N, l, l, -get_(0, 1, N, l, l));
        upd(0, 1, N, r, r, -get_(0, 1, N, r, r));
        upd(0, 1, N, l + 1, r - 1, 1);
    }
    cout << ans << endl;
    return 0;
}
```
:::

## [2. Опять Коля и история](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2011_2)
:::spoiler Разбор
:::info
В этой задаче от Вас требовалось чуть-чуть порисовать и вывести 2 формулы:
1. Случай, когда $N > M$
2. Случай, когда $N <= M$

Асимптотика: $O(1)$.
:::
:::spoiler Авторское решение (Pascal)
```pascal
var m, n, r : longint;
begin
  readln(m, n);
  if m<=n then r:=(m-1)*2 else r:=1+(n-1)*2;
  writeln(r);
end.
```
:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    ll ans = 0;
    if (n == 1 || m == 1) {
        cout << 0 << endl;
        return 0;
    }
    if (n == 2) {
        cout << 2 << endl;
        return 0;
    }
    if (m == 2) {
        cout << 3 << endl;
        return 0;
    }
    if (n - 1 == m && n % 2 == 0) {
        cout << 2 * m << endl;
        return 0;
    }
    if (n + 1 == m && n % 2) {
        cout << n * 2 + 1 << endl;
        return 0;
    }
    if (n > m) {
        ans = 3 + (m - 2) * 2;
        cout << ans << endl;
    } else
        cout << (n - 1) * 2 << endl;
}
```
:::

## [3. Подборка передач](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2011_3)
:::spoiler Разбор
:::info
*Скоро здесь появится разбор задачи*
:::
