Вопрос Олимпиада по информатике №5 фермер джон и древний камень на python 3

[feik]

Ограничение по времени: 1

секунда

Ограничение по памяти: 256

мегабайт

И редко кто бы мог увидеть

Его ночной и тайный путь,

Но берегись его обидеть,

Случайно как‑нибудь толкнуть.

Он скроет жгучую обиду,

Глухое бешенство угроз,

Он промолчит и будет с виду

Недвижен, как простой утес.

Николай Гумилёв, «Камень».

Фермер Джон получил в наследство поле, на котором с незапамятных времен находится один большой и древний камень. По непонятной для самого себя причине Джон боится приближаться к камню, не говоря уже о том, чтобы сдвинуть или избавиться от него. Фермер разбил всё свое поле, которое представляет собой прямоугольник n×m

метров, сеткой на квадраты со стороной один метр. Камень занимает ровно один такой единичный квадрат. Камень находится в строке номер x

и столбце номер y

.

Техника Джона может обработать только прямоугольный участок земли, стороны которого имеют целочисленные значения в метрах и на котором не располагается этот камень. Теперь Джон хочет узнать, сколькими способами он может засеять прямоугольник с расположенными на сетке сторонами, такой, что внутри этого прямоугольника не содержится древний камень.



Формат входных данных

На вход подаются четыре натуральных числа n

, m

, x

, y

, каждое в отдельной строке. 1≤n

, m≤31622

, 1≤x≤n

, 1≤y≤m

.



Формат выходных данных

Выведите одно неотрицательное целое число —

количество способов выделить на поле один прямоугольный участок земли со сторонами, расположенными на сетке, и не содержащий внутри квадрат с камнем. Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64

‑битный тип данных, например, long long в C++, int64

в Free Pascal, long в Java.



Система оценки

Решения, верно работающие при n

, m≤30

, получат не менее 20

баллов.

Решения, верно работающие при n

, m≤300

, получат не менее 40

баллов.

Решения, верно работающие при n

, m≤3000

, получат не менее 60

баллов.

 

[Акс]

на с++
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<int> vi;
const int LG = 19;
const int N = (1 << LG);
vi tr(2 * N, 0);
void upd(int pos, int d){
pos += N;
tr[pos] = d;
pos /= 2;
while(pos > 0){
tr[pos] = tr[2 * pos] + tr[2 * pos + 1];
pos /= 2;
}
}
int get(int l, int r){
l += N;
r += N;
int res = 0;
while(l <= r){
if(l % 2 == 1){
res += tr[l];
}
if(r % 2 == 0){
res += tr[r];
}
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return res;
}
signed main(){
int n, m, x, y;
cin >> n >> m >> x >> y;
int del = x * y * (n - x + 1) * (m - y + 1);
if(n > m){
swap(n, m);
}
for(int i = 1; i <= n; i++){
upd(i, i);
}
int rn = get(1, n);
for(int i = n + 1; i <= m; i++){
upd(i, i);
}
int rm = get(1, m);
int ans = rn * rm - del;
cout << ans;
}

 

[nurda]

Сдал все идеально на 100 из 100, продам все ответы за 300р, писать в телеграм @karsievm

 

[щдлвак]

Фермер Джон и древний камень
Ограничение по времени: 1
секунда
Ограничение по памяти: 256
мегабайт
И редко кто бы мог увидеть
Его ночной и тайный путь,
Но берегись его обидеть,
Случайно как‑нибудь толкнуть.
Он скроет жгучую обиду,
Глухое бешенство угроз,
Он промолчит и будет с виду
Недвижен, как простой утес.
Николай Гумилёв, «Камень».
Фермер Джон получил в наследство поле, на котором с незапамятных времен находится один большой и древний камень. По непонятной для самого себя причине Джон боится приближаться к камню, не говоря уже о том, чтобы сдвинуть или избавиться от него. Фермер разбил всё свое поле, которое представляет собой прямоугольник n×m
метров, сеткой на квадраты со стороной один метр. Камень занимает ровно один такой единичный квадрат. Камень находится в строке номер x
и столбце номер y
.
Техника Джона может обработать только прямоугольный участок земли, стороны которого имеют целочисленные значения в метрах и на котором не располагается этот камень. Теперь Джон хочет узнать, сколькими способами он может засеять прямоугольник с расположенными на сетке сторонами, такой, что внутри этого прямоугольника не содержится древний камень.

Формат входных данных
На вход подаются четыре натуральных числа n
, m
, x
, y
, каждое в отдельной строке. 1≤n
, m≤31622
, 1≤x≤n
, 1≤y≤m
.

Формат выходных данных
Выведите одно неотрицательное целое число —
количество способов выделить на поле один прямоугольный участок земли со сторонами, расположенными на сетке, и не содержащий внутри квадрат с камнем. Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64
‑битный тип данных, например, long long в C++, int64
в Free Pascal, long в Java.

Система оценки
Решения, верно работающие при n
, m≤30
, получат не менее 20
баллов.
Решения, верно работающие при n
, m≤300
, получат не менее 40
баллов.
Решения, верно работающие при n
, m≤3000
, получат не менее 60
баллов.

Ввод
Вывод
3
3
2
3
24
4
5
2
4
102
Код
Python 3






Код из файла
Можно отвечать несколько раз
01 ч 16 мин
Задания по программированию12345

 

[Gr1mm]

тг @succuberry - скину все ответы)