Hi everybody,

This Tuesday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680).

Round will be held at Feb/23/2021 12:05 (Moscow time). You will be given 5 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by grphil, Jatana, rip, Sehnsucht, DebNatkh, KiKoS, wrg0ababd, V--o_o--V, voidmax, meshanya, vintage_Vlad_Makeev under my supervision.

Thanks to adedalic for the round coordination, cdkrot and meshanya for statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Also thanks to Noam527 for providing an additional problem that helped to create (I hope) a balanced problem set for the round.

Good luck everybody!

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD1: Thanks to LHiC, awoo, ScarletS, adarsh7777, kassutta, raj_mehta_ for testing.

UPD2:

Scoring distribution: 500 — 1000 — 1500 — 2250 — 3000

UPD3: Editorial

UPD4: Winners!

Div. 2:

1. InternetPerson10
2. egor95123657
3. hhhyyyfff
4. xXx_KevinDu58_xXx
5. Flying2021

Div. 1 + Div. 2:

1. Um_nik
2. qazswedx2
3. 3.141592653
4. BigBag
5. InternetPerson10

Thanks for the participation!

1492A - Three swimmers was authored by meshanya and prepared by ch_egor

1492B - Card Deck was authored by Noam527 and prepared by ch_egor, adedalic

1492C - Maximum width was authored and prepared by Jatana

1492D - Genius's Gambit was authored by voidmax and prepared by rip

1492E - Almost Fault-Tolerant Database was authored by wrg0ababd and prepared by Sehnsucht

Thanks for the participation!

1445A - Array Rearrangment was authored by meshanya and prepared by ch_egor

1445B - Elimination was authored by Helen Andreeva and prepared by ismagilov.code

1444A - Division was authored by vintage_Vlad_Makeev and prepared by grphil

1444B - Divide and Sum was authored and prepared by NiceClock

1444C - Team-Building was authored by V--o_o--V and prepared by wrg0ababd

1444D - Rectangular Polyline was authored by Zlobober and prepared by DebNatkh

1444E - Finding the Vertex was authored by V--o_o--V and prepared by 300iq

Hi everybody,

This Sunday there will be a XVII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657).

The round will be held at Nov/01/2020 14:05 (Moscow time) and will last for 2 hours. Each division will have 5-6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.

Problems are prepared by vintage_Vlad_Makeev, NiceClock, ismagilov.code, vintage_Vlad_Makeev, KiKoS, wrg0ababd, ch_egor, Roms, voidmax, DebNatkh, Nebuchadnezzar, Endagorion, kraborak, 300iq, cdkrot, LHiC, vintage_Vlad_Makeev, V--o_o--V, grphil under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to adedalic and KAN for the round coordination and verifying statement of original olympiad, meshanya and cdkrot for statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Thanks to Um_nik, satashun, mraron, ustze, Karavaiev, KKiYeer for testing.

UPD2: Scoring distribution:

Div.1: 500 — 1000 — 1500 — 2000 — 3000

Div.2: 500 — 1000 — 1500 — 2000 — 2500

UPD3: Editorial

UPD4: Winners!

Div. 1:

1. hos.lyric
2. Benq
3. ksun48
4. Isonan
5. jiangly

Div. 2:

1. JENXLS
2. God_Of_Blunder
3. jiazp
4. c2020HXW
5. Aishiteru.

Thanks for the participation!

1379A - Acacius and String was authored by ch_egor, meshanya and prepared by ch_egor, vintage_Vlad_Makeev

1379B - Dubious Cyrpto was authored by jury and prepared by DebNatkh

1379C - Choosing flowers was authored and prepared by grphil

1379D - New Passenger Trams was authored by Helen Andreeva and prepared by KiKoS

1379E - Inverse Genealogy was authored and prepared by voidmax and I_love_myself

1379F2 - Chess Strikes Back (hard version) was authored by 300iq and prepared by isaf27

#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

const string T = "abacaba";

int count(const string& s) {
    int cnt = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        if (s.substr(i, T.size()) == T) {
            ++cnt;
        }
    }

    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    for (int tt = 1; tt <= t; ++tt) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        bool F = false;

        for (int i = 0; i + T.size() <= n; ++i) {
            string ss = s;
            bool ok = true;
            for (int j = 0; j < T.size(); j++) {
                if (ss[i + j] != '?' && ss[i + j] != T[j]) {
                    ok = false;
                    break;
                }
                ss[i + j] = T[j];
            }
            if (ok && count(ss) == 1) {
                for (int j = 0; j < n; j++) {
                    if (ss[j] == '?') {
                        ss[j] = 'd';
                    }
                }
                F = true;
                cout << "Yes\n";
                cout << ss << "\n";
                break;
            }
        }
        if (!F) {
            cout << "No\n";
        }
    }

    return 0;
}

Hi!

This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! Olympiad is conducted under the guidance of the Moscow Olympiad Scientific Committee, in particular GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot, voidmax, grphil and, of course, Helen Andreeva.

We are happy to announce the Codeforces Round #657 (Vintage Codeforces Round #3) based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Jul/19/2020 12:00 (Moscow time). You might have already participated in rounds based on the school olympiads, prepared by Moscow Olympiad Scientific Committee (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626) as well as vintage rounds (rounds 626 and 628).

The problems of this olympiad were prepared by DebNatkh, grphil, KiKoS, voidmax, I_love_myself, 300iq, isaf27 under the supervision of grphil.

Thanks ch_egor, vintage_Vlad_Makeev and meshanya for their help in organizing the Codeforces version of this contest and MikeMirzayanov for the Codeforces and Polygon.

Also I would like to thank the Tinkoff company and personally Tatyana TKolinkova Kolinkova for great help with organizing the competition.

Good luck!

UPD1: Scoring distribution: 500 — 750 — 1250 — 1500 — 2500 — (1500 + 1500)

UPD2: Editorial

UPD3: Winners!

Div. 2:

1. imachug
2. yjw0203
3. kaixinqi
4. penguinman
5. Frikkie

Div. 1 + Div. 2:

1. antontrygubO_o
2. risujiroh
3. tmwilliamlin168
4. sansen
5. LayCurse

Thanks for the participation!

1323A - Even Subset Sum Problem was authored and prepared by vintage_Vlad_Makeev

1323B - Count Subrectangles was authored and prepared by vintage_Vlad_Makeev

1322A - Unusual Competitions was authored by vintage_Vlad_Makeev and prepared by DebNatkh

1322B - Present was authored by meshanya and prepared by wrg0ababd

1322C - Instant Noodles was authored by vintage_Vlad_Makeev and prepared by ch_egor

1322D - Reality Show was authored by voidmax and prepared by okwedook

1322E - Median Mountain Range was authored by Sender and prepared by grphil

1322F - Assigning Fares was authored by mingaleg, vintage_Vlad_Makeev and prepared by KiKoS

#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

vector<ll> gao(vector<int> a) {
    int n = a.size();
    vector<ll> res(n + 1);
    int i = 0;
    while (i < n) {
        if (a[i] == 0) {
            i++;
            continue;
        }

        int j = i;
        while (j < n && a[j] == 1) {
            j++;
        }
        for (int len = 1; len <= j - i; len++) {
            res[len] += j - i - len + 1;
        }
        i = j;
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    ll k;
    cin >> n >> m >> k;
    vector<int> a(n);
    vector<int> b(m);
    for (int& x : a) {
        cin >> x;
    }
    for (int& x : b) {
        cin >> x;
    }

    ll ans = 0;

    auto ga = gao(a);
    auto gb = gao(b);
    for (int i = 1; i < ga.size(); i++) {
        if (k % i == 0 && k / i <= m) {
            ans += ga[i] * gb[k / i];
        }
    }

    cout << ans << "\n";
    return 0;
}

Thanks for the participation!

1313A - Fast Food Restaurant was authored by Endagorion and prepared by ch_egor

1313B - Different Rules was authored by meshanya and prepared by DebNatkh

1313C2 - Skyscrapers (hard version) was authored by meshanya and prepared by Sehnsucht

1313D - Happy New Year was authored and prepared by voidmax

1313E - Concatenation with intersection was authored and prepared by isaf27

Hi everybody,

This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594).

Round will be held at Feb/23/2020 12:05 (Moscow time). You will be given 5 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by KiKoS, DebNatkh, grphil, Sehnsucht, voidmax, isaf27 under my supervision.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1:

Scoring distribution: 500 — 1000 — (1000 + 1000) — 2000 — 2500

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD2: Winners!

Div. 2:

1. SARS-CoV-2
2. kvk1920
3. Crazy_Diamond
4. KwanghyunOn
5. pufanyi

Div. 1 + Div. 2:

1. amnesiac_dusk
2. jiangly
3. SARS-CoV-2
4. wiwitrifai
5. cookiedoth

UPD3: Editorial

Thanks for the participation!

1248A - Integer Points was authored by voidmax and prepared by vintage_Vlad_Makeev.

1248B - Grow The Tree was authored by voidmax, cdkrot and prepared by wrg0ababd.

1239A - Ivan the Fool and the Probability Theory was authored and prepared by voidmax.

1239B - The World Is Just a Programming Task (Hard Version) was authored by vintage_Vlad_Makeev and prepared by DebNatkh.

1239C - Queue in the Train was authored by meshanya and prepared by Sehnsucht.

1239D - Catowice City was authored by platypus179 and prepared by Nebuchadnezzar.

1239E - Turtle was authored by voidmax and prepared by cdkrot.

1239F - Swiper, no swiping! was authored and prepared by voidmax.

Hi everybody,

This Sunday there will be a XVII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583).

Round will be held at Oct/20/2019 12:05 (Moscow time) and will last for 2 hours. Each division will have 6 problems.

Problems are prepared by wrg0ababd, vintage_Vlad_Makeev, DebNatkh, grphil, voidmax, vintage_Vlad_Makeev, volcolac, Sehnsucht, isaf27, cdkrot, Flyrise, Nebuchadnezzar, platypus179, Endagorion under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Winners!

Div. 1:

1. tlwpdus
2. rhrnald
3. ainta
4. dorijanlendvaj
5. Retired_MiFaFaOvO
6. maroonrk
7. djq_cpp
8. kort0n
9. Marcin_smu
10. 300iq

Div. 2:

1. lolkekaidarbek
2. qdd
3. mathusalen
4. conan1412yang99
5. fauzdar65
6. DeepThought42
7. mikeleven
8. AnnieCai
9. liuandi
10. jyf111

Editorial will be published soon.

UPD2: Editorial

Thanks for the participation!

1214A - Optimal Currency Exchange was authored and prepared by Helen Andreeva.

1214B - Badges was authored by jury and prepared by Chmel_Tolstiy.

1214C - Bad Sequence was authored by meshanya and prepared by GoToCoding.

1214D - Treasure Island was authored by meshanya and prepared by malcolm.

1214E - Petya and Construction Set was authored and prepared by voidmax.

1214F - Employment was authored and prepared by grphil.

1214G - Feeling Good was authored and prepared by isaf27.

1214H - Tiles Placement was authored and prepared by cdkrot.

Hi everybody!

These days Moscow is conducting the 4th International Olympiad of Metropolises that is an international competition for high school students from biggest cities and capitals all around the world. One of the disciplines of the competition is informatics. Rounds of the competition were prepared by the jury members invited from St. Petersburg, Minsk, Belgrade and Moscow olympiad scientific committee which you may know by Moscow team Olympiad, Open Olympiad in Informatics and Moscow Olympiad for young students (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567).

Scientific Committee of the olympiad consists of: Chmel_Tolstiy, Jelena Hadži-Purić, Elena Andreeva, Zlobober, GlebsHP, andrewzta, meshanya.

The problems were developed by isaf27, cdkrot, manoprenko, GoToCoding, ch_egor, vintage_Vlad_Makeev, voidmax, grphil, malcolm under the guidance of GlebsHP and Zlobober.

Problems were adapted for codeforces by vintage_Vlad_Makeev and cdkrot, also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad. Also, thanks LHiC, voidmax and wrg0ababd for testing!

Good luck and high ratings for everybody!

Round will happen on Sep/04/2019 12:05 (Moscow time) and will last for two and half hours.

The round will consist of 8 problems and will be combined for both divisions. The round is rated for all participants.

P.S. We kindly ask everybody who knows problems of an onsite event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

UPD1: Winners!

1. Retired_MiFaFaOvO
2. gina0605
3. never_giveup
4. Radewoosh
5. kefaa2
6. cz_yixuanxu
7. ko_osaga
8. mango_lassi
9. GoForIt
10. ksun48

Editorial will be published soon.

UPD2: Editorial

(Developing and idea — vintage_Vlad_Makeev)

(Developing and idea — MikeMirzayanov)

(Developing — cdkrot, idea — jury)

(Developing — Sehnsucht, idea — Helen Andreeva)

(Developing and idea — VFeafanov)

(Developing and idea — Sender)

(Developing and idea — voidmax)

Hi everybody,

This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516).

Round will be held at 10:05 UTC on Saturday. You will be given 6 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by vintage_Vlad_Makeev, grphil, cdkrot, VFeafanov, Sehnsucht, Sender, voidmax under my supervision.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Due to some last-minute changes, there will be 7 problems.

UPD2: Winners!

Div 2:

1. Big_black_red_date

2. PinkieRabbit

3. disposrestfuIIy

4. Dobrobober

5. szh0808

6. prodakcin

7. Argentina

8. afedor

9. bigelephant29

10. Young25

Div.1 + Div.2:

1. JustasK

2. BigBag

3. Egor.Lifar

4. Big_black_red_date

5. waynetuinfor

6. dreamoon_love_AA

7. danya090699

8. KrK

9. Farhod_Farmon

10. PinkieRabbit

UPD3: Editorial

Hi everybody,

This Sunday there will be a 16th Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507).

Round will be held at 10:05 UTC on Sunday and will last for 2 hours. Each division will have 6 problems.

Problems are prepared vintage_Vlad_Makeev, Glebodin, Andreikkaa, qoo2p5, mingaleg, Flyrise, cdkrot, achulkov2, grphil, Sehnsucht, Aphanasiy, Sender, DebNatkh, GreenGrape under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: The scoring distribution will be:

500 — 1000 — 1000 — 1500 — 2000 — 2500 for div. 1.

500 — 1000 — 1500 — 2000 — 2000 — 2500 for div. 2.

UPD2: Editorial

UPD3: Winners:

Div. 1:

1. mnbvmar
2. bmerry
3. jcvb
4. tlwpdus
5. WA_TLE

Div. 2:

1. Ebola_Emperor
2. Orange_User
3. orbitingfIea
4. little_waxberry
5. fnch

(Developing — vintage_Vlad_Makeev, ch_egor, V--o_o--V, demon1999)

(Developing — ch_egor)

(Developing — ch_egor)

(Developing — halin.george)

(Developing — Sehnsucht)

(Developing — cdkrot, ch_egor)

Hello everybody!

Tomorrow in unusual time round will be held using problemset of Moscow programming competition for school students of grades from 6 to 9. Do not be tricked by the age range of the participants, Moscow jury always tries its best to select interesting problems of various topics. Problems were developed by halin.george, Sehnsucht, cdkrot, vintage_Vlad_Makeev and ch_egor.

Thanks to MikeMirzayanov for an excellent platform Codeforces for contests and an excellent platform Polygon, which greatly simplifies the preparation of contests.

Thanks to V--o_o--V for reducing the statements and translating them into english.

Hope to see you in the standings!

UPD1: Scoring 500-1250-1250-1500-2000-2750

UPD2: Our problemsetters are tired because of olympiad, so editorial will be a bit later. We apologize for it.

Winners:

Division 2:

1. zzs_dasc

2. Kataoka_Yuuki

3. Akikaze

4. tshil

5. WatchClannad

Division 1 + 2 (unofficial):

1. uwi

2. zzs_dasc

3. fmota

4. Kataoka_Yuuki

5. eddy1021

UPD3: Editorial

If you notice typos or errors, please send a private message.

Div2A Free Ice Cream

Author: cdkrot
Developer: ch_egor

You just needed to implement the actions described in statement.

If you solution failed, then you probably forgot to use 64-bit integers or made some small mistake.

Correct solution:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 1005;

int n, x, sad;
int64 answer;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d %d\n", &n, &x);

	answer = x;
	sad = 0;

	int cur;
	char type;
	for (int i = 0; i < n; ++i)
	{
		scanf("%c %d\n", &type, &cur);
		if (type == '+')
		{
			answer += cur;
		}
		else if (answer >= cur)
		{
			answer -= cur;
		}
		else
		{
		    ++sad;
		}
	}

	cout << answer << " " << sad << "\n";

	fclose(stdin);
	fclose(stdout);

	return 0;
}

import sys

def main():
    n, answer = map(int, sys.stdin.readline().split())
    sad = 0

    for i in range(n):
        type_of, cur = sys.stdin.readline().split()
        cur = int(cur)
        if type_of == "+":
            answer += cur
        elif answer >= cur:
            answer -= cur
        else:
            sad += 1

    sys.stdout.write(str(answer) + " " + str(sad))

main()

Div2B Little Robber Girl's Zoo

Author: ch_egor
Developer: ch_egor

We need to sort an array with strange operations — namely, to swap elements with even and odd indices in subarray of even length. Note that we can change the 2 neighboring elements, simply doing our exchange action for subarray of length 2 containing these elements. Also, note that n ≤ 100, and it is permission to do 20 000 actions, therefore, we can write any quadratic sort, which changes the neighboring elements in each iteration (bubble sort for example).
Complexity O(n²)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 105;

int n;
int arr[MAX_N];

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d", &n);

	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &arr[i]);
	}

	for (int i = n - 1; i > 0; --i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				printf("%d %d\n", j + 1, j + 2);
			}
		}
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}

n = int(input())
arr = list(map(int, input().split()))

for i in range(n - 1, 0, -1):
    for j in range(i):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            print(j + 1, j + 2)

Bonus: Is anyone able to search the shortest solution of this problem? If yes, what complexity?

Div2C Robbers' watch/Div1A Robbers' watch

Author: cdkrot
Developer: themikemikovi4

In this problem we use the septimal number system. It is a very important limitation. Let's count how many digits are showed on the watch display and call it cnt. If cnt more than 7, the answer is clearly 0 (because of pigeonhole principle). If cnt is not greater than 7, then you can just bruteforces all cases.
Depending on the implementation it will be O(BASE BASE^BASE), O(BASE^BASE) or O(BASE BASE!), where BASE = 7. Actually the most simple implementation is just to cycle between all posible hour:minute combinations and check them.
In the worst case, it will work in O(BASE BASE^BASE).

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n, m;
    cin >> n >> m;

    size_t len1 = 1, len2 = 1;
    for (size_t a = 7; a < n; a *= 7)
        len1 += 1;
    for (size_t b = 7; b < m; b *= 7)
        len2 += 1;

    size_t ans = 0;
    if (len1 + len2 <= 7)
        for (size_t i = 0; i != n; ++i)
            for (size_t j = 0; j != m; ++j) {
                vector<size_t> used(7, 0);
                
                for (size_t a = i, k = 0; k != len1; a /= 7, ++k)
                    used[a % 7] += 1;
                for (size_t b = j, k = 0; k != len2; b /= 7, ++k)
                    used[b % 7] += 1;
                
                if (*std::max_element(used.begin(), used.end()) <= 1)
                    ++ans;
            }
    
    cout << ans << "\n";
    
    return 0;
}

BASE = 7

def itov(x):
    digits = []
    if x == 0:
        digits.append(0)
    while x > 0:
        digits.append(x % BASE)
        x //= BASE
    digits.reverse()
    return digits

def gen(pos = 0, minute = False, smaller = False):
    max_val = max_minute if minute else max_hour
    if pos >= len(max_val):
        if minute:
            return 1
        else:
            return gen(0, True)
    else:
        ans = 0
        for digit in range(BASE):
            if not used[digit] and (smaller or digit <= max_val[pos]):
                used[digit] = True
                ans += gen(pos + 1, minute, smaller or digit < max_val[pos])
                used[digit] = False
        return ans

n, m = map(int, input().split())
n -= 1
m -= 1
used = [False] * BASE
max_hour = itov(n)
max_minute = itov(m)
print(gen())

Bonus: Suppose the base is not fixed. Solve a problem with n ≤ 10⁹, m ≤ 10⁹, BASE ≤ 10⁹. Can you do it in ?

Div2D Kay and Snowflake/Div1B Kay and Snowflake

Author: cdkrot
Developers: ch_egor, cdkrot

There are many possible approaches.

Solution by cdkrot:

Look at the all candidates for the centroid of the vertices v subtree. The size of centroid subtree must be at least of the vertex v subtree size. (If it isn't, then after cutting the upper part will have too big size)

Choose the vertex with the smallest subtree size satisfying the constraint above. Let's prove, that this vertex is centroid indeed. If it isn't, then after cutting some part will have subtree size greater than of subtree size of query vertex. It isn't upper part (because of constraint above), it is one of our sons. Ouch, it's subtree less than of selected vertex, and it's still greater than of subtree size of query vertex. Contradiction.

So we find a centroid.
We write the euler tour of tree and we will use a 2D segment tree in order to search for a vertex quickly.
Complexity

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

const size_t MAXN = (1 << 19);
vector<size_t> graph[MAXN];

vector<pair<size_t, size_t>> segm[2 * MAXN - 1];

#define time TIME_FUCKLIBC

pair<size_t, size_t> times[MAXN];
size_t time = 0;

size_t sizes[MAXN];

void dfs(size_t v) {
    size_t sz = 1;
    
    times[v].first = time++;

    for (size_t u: graph[v]) {
        dfs(u);
        sz += sizes[u];
    }
    
    times[v].second = time;
    segm[MAXN - 1 + times[v].first].emplace_back(sz, v);
    
    sizes[v] = sz;
}

void buildseg(size_t node, size_t L, size_t R) {
    if (L != R - 1) {
        size_t mid = L + (R - L) / 2;
        buildseg(2 * node + 1, L, mid);
        buildseg(2 * node + 2, mid, R);
        
        segm[node].resize(segm[2 * node + 1].size() + segm[2 * node + 2].size());
        std::merge(segm[2 * node + 1].begin(), segm[2 * node + 1].end(), segm[2 * node + 2].begin(), segm[2 * node + 2].end(), segm[node].begin());
    }
}

pair<size_t, size_t> lowerb(size_t node, size_t L, size_t R, size_t rl, size_t rr, pair<size_t, size_t> minval) {
    if (rl <= L and R <= rr) {
        auto it = std::lower_bound(segm[node].begin(), segm[node].end(), minval);
        if (it == segm[node].end())
            return make_pair(SIZE_MAX, SIZE_MAX);
        else
            return *it;
    }
    if (R <= rl or rr <= L)
        return make_pair(SIZE_MAX, SIZE_MAX);

    size_t mid = L + (R - L) / 2;
    return min(lowerb(2 * node + 1, L, mid, rl, rr, minval)
              ,lowerb(2 * node + 2, mid, R, rl, rr, minval));
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n, q;
    cin >> n >> q;
    
    for (size_t i = 1; i != n; ++i)
        graph[input<size_t>() - 1].push_back(i);

    dfs(0);
    buildseg(0, 0, MAXN);
    
    for (size_t i = 0; i != q; ++i) {
        size_t v = input<size_t>() - 1;
        cout << lowerb(0, 0, MAXN, times[v].first, times[v].second, make_pair((sizes[v] + 1) / 2, 0)).second + 1 << "\n";
    }
    
    return 0;
}

You can consider all answers by one in dfs using this idea. Use std::set for pair (subtree size, vertex number) and at each vertex merge sets obtained from children. (Also known as "merging sets" idea)
Thus we get the answers for all vertex and we need only output answers for queries.
Complexity

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

set<pair<size_t, size_t>> solve(const vector<vector<size_t>>& graph, vector<size_t>& ans, size_t v) {
    set<pair<size_t, size_t>> cur;

    for (size_t u: graph[v]) {
        auto ch = solve(graph, ans, u);
        if (not (ch.size() < cur.size()))
            std::swap(ch, cur);
        
        for (auto elem: ch)
            cur.insert(elem);
    }

    size_t sz = cur.size() + 1;
    cur.emplace(sz, v);

    ans[v] = cur.lower_bound(make_pair((sz + 1) / 2, 0))->second;
    
    return std::move(cur);
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n, q;
    cin >> n >> q;
    
    vector<vector<size_t>> graph(n);
    for (size_t i = 1; i != n; ++i)
        graph[input<size_t>() - 1].push_back(i);

    vector<size_t> ans(n, SIZE_MAX);

    solve(graph, ans, 0);
    
    for (size_t i = 0; i != q; ++i)
        cout << ans[input<size_t>() - 1] + 1 << "\n";
    
    return 0;
}

Solution by ch_egor:
Solve it for all subtrees. We can solve the problem for some subtree, after solving the problem for all of it's children. Let's choose the heaviest child. Note that the centroid of the child after a certain lifting goes into our centroid. Let's model the lifting.
Thus we get the answers for all vertex and we need only output answers for queries.
Complexity O(n + q)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 300 * 1000 + 5;
const int MAX_Q = 300 * 1000 + 5;

int n, q;
vector<int> graph[MAX_N];
int size_of[MAX_N];
int prev_of[MAX_N];
int big_subtree[MAX_N];
int centroid[MAX_N];

bool is_centroid_of_subtree(int v, int c)
{
	return ((size_of[v] - size_of[c]) * 2 <= size_of[v] && big_subtree[c] * 2 <= size_of[v]);
}

void dfs_calc(int v, int p)
{
	big_subtree[v] = 0;
	size_of[v] = 1;
	prev_of[v] = p;

	for (int i = 0; i < graph[v].size(); ++i)
	{
		dfs_calc(graph[v][i], v);
		size_of[v] += size_of[graph[v][i]];
		big_subtree[v] = max(big_subtree[v], size_of[graph[v][i]]);
	}
}

void dfs_centroid(int v)
{
	if (size_of[v] == 1)
	{
		centroid[v] = v;
	}
	else
	{
		int ptr = 0;
		for (int i = 0; i < graph[v].size(); ++i)
		{
			dfs_centroid(graph[v][i]);
			if (size_of[graph[v][ptr]] < size_of[graph[v][i]])
			{
				ptr = i;
			}
		}

		int c = centroid[graph[v][ptr]];

		while (!is_centroid_of_subtree(v, c))
		{
			c = prev_of[c];
		}

		centroid[v] = c;
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d %d", &n, &q);

	int v;
	for (int i = 0; i < n - 1; ++i)
	{
		scanf("%d", &v);
		graph[v - 1].push_back(i + 1);
	}

	dfs_calc(0, 0);
	dfs_centroid(0);

	for (int i = 0; i < q; ++i)
	{
		scanf("%d", &v);
		printf("%d\n", centroid[v - 1] + 1);
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}

Div2E Optimal Point/Div1C Optimal Point

Author: cdkrot
Developer: cdkrot

Let's say few words about ternary search. It works correctly, but too slow.
It's complexity is , where n = 10⁵, and v = 10¹⁸.
Don't use it.

Solution.
1) Let's make binary search on answer
2) Consider areas of "good" points (with dist  ≤ mid) for each source point.
3) Intersect those areas and check for solution.

This area can be decsribed by following inequalities:
(You can achieve them if you expand modules in inequality "manhattan distance <= const")

.. denote some constants.

If you intersect set of such system, you will get system of the same form, so let's learn how to solve such system.

Let's replace some variables:

Then:

Now the system transforms into:

We need to check if the system has solution in integers, also the numbers a, b, c must be of the same parity (have equal remainder after division by 2). (This is required for x, y, z to be integers too)

Let's get rid of parity constraint. Bruteforce the parity of a, b, c (two cases)

Make following replacement: a = 2a' + r, b = 2b' + r, c = 2c' + r, where r = 0 or r = 1. Substitute in equations above, simplify, and gain the same system for a', b', c' without parity constraint.

And now the system can be solved greedy (At first set a, b, c with minimum, and then raise slowly if necessary).

Total complexity is .

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

struct coord {
    int64_t x;
    int64_t y;
    int64_t z;
};

struct equation {
    pair<int64_t, int64_t> S;
    pair<int64_t, int64_t> a;
    pair<int64_t, int64_t> b;
    pair<int64_t, int64_t> c;
};

vector<coord> list;

equation operator+(const equation& e1, const equation& e2) {
    equation res;
    res.S = {max(e1.S.first, e2.S.first), min(e1.S.second, e2.S.second)};
    res.a = {max(e1.a.first, e2.a.first), min(e1.a.second, e2.a.second)};
    res.b = {max(e1.b.first, e2.b.first), min(e1.b.second, e2.b.second)};
    res.c = {max(e1.c.first, e2.c.first), min(e1.c.second, e2.c.second)};
    return res;
}

coord get_solution(const equation& eq) {
    if ((eq.S.first > eq.S.second)
     or (eq.a.first > eq.a.second)
     or (eq.b.first > eq.b.second)
     or (eq.c.first > eq.c.second))
        return coord {INT64_MAX, INT64_MAX, INT64_MAX};
        
     if ((eq.a.first + eq.b.first + eq.c.first > eq.S.second)
     or (eq.a.second + eq.b.second + eq.c.second < eq.S.first))
        return coord {INT64_MAX, INT64_MAX, INT64_MAX};

     coord res;
     res.x = eq.a.first;
     res.y = eq.b.first;
     res.z = eq.c.first;
     int64_t delta = max(int64_t(0), eq.S.first - res.x - res.y - res.z);

     res.x += min(delta, eq.a.second - eq.a.first);
     delta -= min(delta, eq.a.second - eq.a.first);
     res.y += min(delta, eq.b.second - eq.b.first);
     delta -= min(delta, eq.b.second - eq.b.first);
     res.z += min(delta, eq.c.second - eq.c.first);
     delta -= min(delta, eq.c.second - eq.c.first);

     assert(delta == 0);
     
     return res;
}

int64_t DIV2(int64_t arg) {
    return (arg - (arg & 1)) / 2;
}

coord can(int64_t MAXANS) {
    equation eq;
    eq.S = eq.a = eq.b = eq.c = {INT64_MIN, INT64_MAX};
    
    for (const coord& crd: list) {
        equation nw;
        nw.S = { crd.x + crd.y + crd.z - MAXANS,  crd.x + crd.y + crd.z + MAXANS};
        nw.a = {-crd.x + crd.y + crd.z - MAXANS, -crd.x + crd.y + crd.z + MAXANS};
        nw.b = { crd.x - crd.y + crd.z - MAXANS,  crd.x - crd.y + crd.z + MAXANS};
        nw.c = { crd.x + crd.y - crd.z - MAXANS,  crd.x + crd.y - crd.z + MAXANS};
        
        eq = eq + nw;
    }

    for (int64_t r = 0; r <= 1; ++r) {
        equation tr = eq;

        tr.S.first  = DIV2(tr.S.first - 3 * r + 1);
        tr.a.first  = DIV2(tr.a.first - r + 1);
        tr.b.first  = DIV2(tr.b.first - r + 1);
        tr.c.first  = DIV2(tr.c.first - r + 1);

        tr.S.second = DIV2(tr.S.second - 3 * r);
        tr.a.second = DIV2(tr.a.second - r);
        tr.b.second = DIV2(tr.b.second - r);
        tr.c.second = DIV2(tr.c.second - r);

        coord sol = get_solution(tr);
        if (sol.x != INT64_MAX) {
            coord ans;
            ans.x = r + sol.y + sol.z;
            ans.y = r + sol.x + sol.z;
            ans.z = r + sol.x + sol.y;

            return ans;
        }
    }
    return coord {INT64_MAX, INT64_MAX, INT64_MAX};
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    list.reserve(100000);
    
    for (size_t T = input<size_t>(); T != 0; --T) {
        list.resize(input<size_t>());
        
        for (coord& crd: list)
            cin >> crd.x >> crd.y >> crd.z;

        int64_t L = -1; // definitely imposible
        int64_t R = 3 * int64_t(1000 * 1000 * 1000) * int64_t(1000 * 1000 * 1000) + 10; // definitely possible

        while (R - L > 1) {
            int64_t M = L + (R - L) / 2;
            if (can(M).x != INT64_MAX)
                R = M;
            else
                L = M;
        }
        coord ans = can(R);
        cout << ans.x << " " << ans.y << " " << ans.z << "\n";
    }
    
    return 0;
}

Bonus. This task can be solved in a lot of modifications, for example euclidian distance instead of manhattan, 2d instead of 3d, floats instead of integers. How to solve this varations?

Div1D Kay and Eternity

Authors: platypus179, Endagorion
Developer: platypus179

Let's solve this problem with scanline. Go through all rows from left to right and maintain the array in which in j index we will store the number of points in a square with bottom left coordinate (i, j), where i is current row of scanline.

This takes O(MAXCORD²) time. Note that the set of squares that contain some of the shaded points is not very large, namely — if the point has coordinates (x, y), then the set of left bottom corners of square is defined as {(a, b)|x - k + 1 <  = a <  = x, y - k + 1 <  = b <  = y}. Let's consider each point (x, y) as the 2 events:
Add one to the all elements with indexes from y - k + 1 to y on the row x - k + 1 and take one at the same interval on the row x + 1. How to calculate answer? Suppose we update the value of a cell on the row a, and before it was updated the value x on the row b. Let add to the answer for the number of squares containing x points value a - b. We can implement the addition of the segment directly and have O(nk) for processing all the events that fit in time limit. To get rid of O(MAXCORD) memory, we need to write all interested in the coordinates before processing events (them no more than nk) and reduce the coordinates in the events. It takes time and O(nk) memory. Now we can execute the previous point in O(nk) memory.
Complexity is time and O(nk) memory.

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

#define NotANumber -1791791791

struct query {
    int row, l, r; bool a;
    int lbl, ubr;
    query(int _row, int _l, int _r, bool _a) {row = _row; l = _l; r = _r; a = _a;}
    bool operator<(const query& other) const {
        return row < other.row;
    }
};

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    vector<pair<int, int> > points(n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &points[i].first, &points[i].second);

    sort(points.begin(), points.end());
    vector<int> xcoords;
    for (int i = 0; i < n; i++) {
        int st;
        if (xcoords.empty())
            st = points[i].first - k + 1;
        else
            st = max(xcoords.back() + 1, points[i].first - k + 1);
        for (int j = st; j <= points[i].first; j++)
            xcoords.push_back(j);
    }

    vector<query> qs;
    for (int i = 0; i < n; i++) {
        qs.push_back(query(points[i].second - k + 1, points[i].first - k + 1, points[i].first, 1));
        qs.push_back(query(points[i].second + 1, points[i].first - k + 1, points[i].first, 0));
    }

    for (query & q : qs) {
        q.lbl = lower_bound(xcoords.begin(), xcoords.end(), q.l) - xcoords.begin();
        q.ubr = upper_bound(xcoords.begin(), xcoords.end(), q.r) - xcoords.begin();
    }
    
    int xcdssz = xcoords.size();
    xcoords.clear();
    xcoords.shrink_to_fit();

    sort(qs.begin(), qs.end());

    vector<int> vec(xcdssz, 0);
    vector<int> lastchanged(xcdssz, NotANumber);
    vector<ll> ans(n);

    for (query q : qs) {
        int lbl = q.lbl;
        int ubr = q.ubr;
        for (int i = lbl; i < ubr; i++) {
            if (lastchanged[i] != NotANumber && vec[i] != 0) {
                ans[vec[i] - 1] += q.row - lastchanged[i];
            }
            if (q.a)
                vec[i]++;
            else
                vec[i]--;
            lastchanged[i] = q.row;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%lld ", ans[i]);
    printf("\n");
    return 0;
}

Bonus: time and O(n) memory.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int int64;
typedef long double double80;

const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 1000 * 100 + 5;
const int MAX_K = 305;

/** Interface */

inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt(T x);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void flush();

/** Read */

static const int buf_size = 20 * 1000 * 1000;

inline int getChar()
{
	static char buf[buf_size];
	static int len = 0, pos = 0;
	if (pos == len)
		pos = 0, len = fread(buf, 1, buf_size, stdin);
	if (pos == len)
		return -1;
	return buf[pos++];
}

inline int readChar()
{
	int c = getChar();
	while (c <= 32)
		c = getChar();
	return c;
}

template <class T>
inline T readInt()
{
	int s = 1, c = readChar();
	T x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}

inline int64 readInt64()
{
	int s = 1, c = readChar();
	int64 x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar(int x)
{
	if (write_pos == buf_size)
		fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
	write_buf[write_pos++] = x;
}

inline void flush()
{
	if (write_pos)
		fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}

template <class T>
inline void writeInt(T x)
{
	if (x < 0)
		writeChar('-'), x = -x;

	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
}

inline void writeInt64(int64 x)
{
	if (x < 0)
		writeChar('-'), x = -x;

	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
}

inline void writeWord(const char *s)
{
	while (*s)
		writeChar(*s++);
}

struct point
{
	int x;
	int y;
};

struct ask
{
	int l;
	int r;
	int ptr;
	int type;
};

bool cmp(const ask &a, const ask &b)
{
	return a.ptr < b.ptr;
}

int n, k;
point arr[MAX_N];
int cord[MAX_N * 2];
ask asks[MAX_N * 2];
int cord_len = 0;
int asks_len = 0;
bool have_prev_cord[MAX_N * 2];
bool have_prev_line[MAX_N * 2];
int last_of_cord[MAX_N * 2];
int last_of_line[MAX_N * 2];
int at_cord[MAX_N * 2];
int at_line[MAX_N * 2];
int64 answer[MAX_N];

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	n = readInt();
	k = readInt();

	for (int i = 0; i < n; ++i)
	{
		arr[i].x = readInt();
		arr[i].y = readInt();
		cord[cord_len++] = arr[i].x;
		cord[cord_len++] = arr[i].x - k + 1;
	}

	sort(cord, cord + 2 * n);
	cord_len = unique(cord, cord + 2 * n) - cord;
	
	for (int i = 0; i < n; ++i)
	{
		asks[asks_len].l = lower_bound(cord, cord + cord_len, arr[i].x - k + 1) - cord;
		asks[asks_len].r = lower_bound(cord, cord + cord_len, arr[i].x) - cord;
		asks[asks_len].ptr = arr[i].y - k + 1;
		asks[asks_len].type = 1;
		++asks_len;
		asks[asks_len].l = asks[asks_len - 1].l;
		asks[asks_len].r = asks[asks_len - 1].r;
		asks[asks_len].ptr = arr[i].y + 1;
		asks[asks_len].type = -1;
		++asks_len;
	}

	sort(asks, asks + asks_len, cmp);
	memset(answer, 0, sizeof(answer));
	memset(last_of_cord, 0, sizeof(last_of_cord));
	memset(last_of_line, 0, sizeof(last_of_line));
	memset(at_cord, 0, sizeof(at_cord));
	memset(at_line, 0, sizeof(at_line));
	memset(have_prev_cord, 0, sizeof(have_prev_cord));
	memset(have_prev_line, 0, sizeof(have_prev_cord));

	for (int i = 0; i < asks_len; ++i)
	{
		for (int j = asks[i].l; j <= asks[i].r; ++j)
		{
			if (!have_prev_cord[j])
			{
				have_prev_cord[j] = true;
				last_of_cord[j] = asks[i].ptr;
				at_cord[j] += asks[i].type;
			}
			else
			{
				answer[at_cord[j]] += asks[i].ptr - last_of_cord[j];

				last_of_cord[j] = asks[i].ptr;
				at_cord[j] += asks[i].type;
			}
		

			if (j != asks[i].r)
			{
				if (!have_prev_line[j])
				{
					have_prev_line[j] = true;
					last_of_line[j] = asks[i].ptr;
					at_line[j] += asks[i].type;
				}
				else
				{
					answer[at_line[j]] += 1ll * (cord[j + 1] - cord[j] - 1) * (asks[i].ptr - last_of_line[j]);

					last_of_line[j] = asks[i].ptr;
					at_line[j] += asks[i].type;
				}
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		writeInt64(answer[i]);
		writeChar(' ');
	}

	flush();

	fclose(stdin);
	fclose(stdout);

	return 0;
}

Div1E Travelling Through the Snow Queen's Kingdom

Authors: cdkrot, GlebsHP
Developers: ch_egor, cdkrot

Unfortunately, due to my, cdkrot, failure, it was possible to get Ac with O(nm) solution, I apologise for that.

We propose following solution:
Let's solve task with divide & conquer. At first let's lift l to the first index, where s was mentioned And lower the r to the last index, where t was mentioned. This will not affect answers, but will make implementation much more easy.

Let's look on all queries. For each query consider it's location relative to centre of edges array. If it's stricly on the left half or on the right half, then solve recursively (You need to implement function like solve(requests, l, r)).

How to answer on query, if it contains the centre? Let's precalculate two dp's:

dp_r[i] =  bitset of vertices you can from to the v_i or u_i with l = m and r = i.

dp_l[i] =  bitset of vertices you can go to starting from v_i or u_i with l = i and r = m - 1

v_i and u_i are vertices of i'th edge.

Using this dp the answer is yes if and ony if dp_l[l][u] = true and dp_r[r][u] = true for some u.

All above can be implemented using bitwise operations.
So the time is

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
#include <bitset>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

#define size_t uint32_t

struct Req {
    size_t L;
    size_t R;
    size_t S;
    size_t T;
    size_t ID;
};

struct Edge {
    size_t v;
    size_t u;
    size_t prev1;
    size_t prev2;
    size_t next1;
    size_t next2;
};

const size_t MAXQ = 200000;
const size_t MAXN = 1000;
const size_t MAXM = 200000;

char answers[MAXQ];
Edge list[MAXM];
vector<size_t> last[MAXN];

std::bitset<MAXN> masks_r[MAXM / 2 + 10];
std::bitset<MAXN> masks_l[MAXM / 2 + 10];

void solve_layer(vector<Req>& requests, size_t l, size_t m, size_t r) {
    bool has = false;
    for (size_t i = 0; i != requests.size(); ++i)
        has or_eq (requests[i].L <= m - 1 and requests[i].R >= m);
    if (not has)
        return;
    
    for (size_t i = 0; i != r - m; ++i) {
        masks_r[i] = std::bitset<MAXN>();
        if (list[m + i].prev1 >= m and list[m + i].prev1 != std::numeric_limits<size_t>::max())
            masks_r[i] |= masks_r[list[m + i].prev1 - m];
        if (list[m + i].prev2 >= m and list[m + i].prev2 != std::numeric_limits<size_t>::max())
            masks_r[i] |= masks_r[list[m + i].prev2 - m];

        masks_r[i][list[m + i].v] = true;
        masks_r[i][list[m + i].u] = true;
    }
    
    for (size_t z = 0; z != m - l; ++z) {
        size_t i = (m - l) - 1 - z;
        masks_l[i] = std::bitset<MAXN>();
        
        if (list[l + i].next1 < m)
            masks_l[i] |= masks_l[list[l + i].next1 - l];
        if (list[l + i].next2 < m)
            masks_l[i] |= masks_l[list[l + i].next2 - l];
        masks_l[i][list[l + i].v] = true;
        masks_l[i][list[l + i].u] = true;
    }

    for (size_t i = 0; i != requests.size();)
        if (requests[i].L <= m - 1 and requests[i].R >= m) {
            answers[requests[i].ID] = (masks_r[requests[i].R - m] & masks_l[requests[i].L - l]).any();
            std::swap(requests[i], requests.back());
            requests.pop_back();
        } else {
            ++i;
        }
}

void solve(vector<Req>& requests, size_t l, size_t r) {
    if (l == r - 1) {
        for (auto& req: requests)
            answers[req.ID] = (req.S == list[l].v or req.S == list[l].u)
                          and (req.T == list[l].v or req.T == list[l].u);
        return;
    }
    size_t m = l + (r - l) / 2;
    // [l, m), [m, r).

    solve_layer(requests, l, m, r);

    vector<Req> right;
    for (size_t i = 0; i != requests.size();)
        if (requests[i].L >= m) {
            right.push_back(requests[i]);
            std::swap(requests[i], requests.back());
            requests.pop_back();
        } else {
            ++i;
        }

    requests.shrink_to_fit();
    solve(requests, l, m);
    solve(right, m, r);
}

int main() {
    size_t n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    assert(n <= MAXN);
    assert(q <= MAXQ);
    assert(m <= MAXM);
    
    std::fill(answers, answers + q, 16);
    
    for (size_t i = 0; i != m; ++i) {
        scanf("%d %d", &list[i].v, &list[i].u);
        --list[i].v, --list[i].u;
        list[i].prev1 = list[i].prev2 = list[i].next1 = list[i].next2 = std::numeric_limits<size_t>::max();
        
        if (not last[list[i].v].empty()) {
            list[i].prev1 = last[list[i].v].back();
            
            if (list[last[list[i].v].back()].v == list[i].v)
                list[last[list[i].v].back()].next1 = i;
            else {
                list[last[list[i].v].back()].next2 = i;
            }
        }

        if (not last[list[i].u].empty()) {
            list[i].prev2 = last[list[i].u].back();
            
            if (list[last[list[i].u].back()].v == list[i].u)
                list[last[list[i].u].back()].next1 = i;
            else {
                list[last[list[i].u].back()].next2 = i;
            }
        }
        
        last[list[i].v].push_back(i);
        last[list[i].u].push_back(i);
    }

    vector<Req> requests;
    for (size_t i = 0; i != q; ++i) {
        Req req;
        scanf("%d %d %d %d", &req.L, &req.R, &req.S, &req.T);
        --req.L, --req.R, --req.S, --req.T;
        req.ID = i;
        
        auto it1 = std::lower_bound(last[req.S].begin(), last[req.S].end(), req.L);
        auto it2 = std::upper_bound(last[req.T].begin(), last[req.T].end(), req.R);

        if (it1 == last[req.S].end() or it2 == last[req.T].begin())
            answers[i] = false;
        else {
            req.L = *it1;
            req.R = *std::prev(it2);
            if (req.L > req.R)
                answers[i] = false;
            else
                requests.push_back(req);
        }
    }
    
    solve(requests, 0, m);

    for (size_t i = 0; i != q; ++i) {
        printf("%s", (answers[i] ? "Yes\n" : "No\n"));
    }
    
    return 0;
}