Областная олимпиада по информатике 2020 год, 9-11 классы

Задача A. Кролики

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

2 секунды

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

256 мегабайт

У Айбара есть сад, который состоит из $K$ подряд идущих грядок. В саду живут $n$ кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано $q$ запросов, которые надо обработать. Они бывают следующих типов:

• Кролик номер $x\; (1 <= x <= n)$ перешел на одну грядку налево или направо. При этом гарантируется, что кролик не выйдет за пределы сада
• Посчитать количество кроликов на отрезке от грядки $l$ до грядки $r$ $(1 <= l <= r <= K)$ включительно.

Формат входного файла

В первой строке входных данных даны два числа - $n$ и $K$. \\ Далее во второй строке указаны $n$ чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число $q$ и $q$ строк описывающих запросы. Запросы задаются в следующем формате:

• $\texttt{L } x$ - сдвинуть кролика номер $x$ на одну грядку налево
• $\texttt{R } x$ - сдвинуть кролика номер $x$ на одну грядку направо
• $\texttt{G } l\; r$ - Посчитать и вывести количество кроликов на отрезке от грядки $l$ до грядки $r$ включительно.

Формат выходного файла

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

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

Подзадача 1 (20 баллов) — $1 <= n, K, q <= 1000$ Подзадача 2 (20 баллов) — $1 <= n, K, q <= 5 * 10^5$, отсутствуют запросы сдвига кролика Подзадача 3 (60 баллов) — $1 <= n, K, q <= 5 * 10^5$

Пример:

Вход

3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7

Ответ

1
3

( Sanjar Bidaibek )

Комментарий/решение

показать/скрыть код

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 100005;
const ll NN = 105;
const double pi = 3.14159;
const ll MAX = 2e5 + 123;
const ll MOD = 1e9 + 7;
const ll INF = 1000000000000000000;

int n, m, q, a[5 * N], f[5 * N];

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]), f[a[i]] ++;
    for (int i = 1; i <= m; i ++) f[i] += f[i - 1];
    scanf ("%d", &q);
    while (q --)
    {
        char c;
        int l, r;
        scanf(" %c", &c);
        if (c == 'G')
        {
            scanf ("%d%d", &l, &r);
            printf ("%d\n", f[r] - f[l - 1]);
        }
        else if (c == 'R')
        {
            scanf ("%d", &r);
            a[r] ++;
            f[a[r] - 1] --;
        }
        else
        {
            scanf ("%d", &l);
            a[l] --;
            f[a[l]] ++;
        }
    }
}

DELETED

Дерево отрезков ;)

показать/скрыть код

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define ld long double
#define lb lower_bound
#define ub upper_bound
#define ar array
#define sz(x) (int)x.size()
#define bit(x) __builtin_popcount(x)
#define all(x) (x).begin(), (x).end()
#define FOR(l,r,c) for(int c=(l);c<=(r);c++)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
using ll = long long;
#define int ll
const int N = 2e6 + 7;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 7;
const int inf1 = 2e9 + 7;
const ll inf2 = 2e10 + 7;
const ll inf3 = 2e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;

int b[N], a[N], t[4 * N];
void build (int v, int tl, int tr) {
    if (tl == tr) t[v]=a[tl];
    else {
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        t[v]=t[v*2]+t[v*2+1];
    }
}
int get(int l, int r, int v, int tl, int tr) {
    if (l <= tl and tr <= r) return t[v];
    if (tr < l || r < tl) return 0;
    int tm = (tl + tr) / 2;
    int q1 = get(l,r,v*2,tl,tm);
    int q2 = get(l,r,v*2+1,tm+1,tr);
    return q1+q2;
}
void upd(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        t[v] += val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            upd(v*2,tl,tm,pos,val);
        } else {
            upd(v*2+1,tm+1,tr,pos,val);
        }
        t[v]=t[v+v]+t[v+v+1];
    }
}
void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> b[i];
        a[b[i]]++;
    }
    build(1,1,k);
    int q;
    cin >> q;
    while (q --) {
        char c;
        cin >> c;
        int x, l, r;
        if (c == 'L') {
            cin >> x;
            int val = b[x];
            upd(1,1,k,b[x],-1);b[x] --;
            upd(1,1,k,b[x],1);
        } else if (c == 'R') {
            cin >> x;
            int val = b[x];
            upd(1,1,k,b[x],-1);b[x] ++;
            upd(1,1,k,b[x],1);
        } else {
            cin >> l >> r;
            cout << get(l,r,1,1,k) << '\n';
        }
    }
}
main(){
    speed;
    int tt = 1;
    //cin >> tt;
    while (tt --){
        solve();
        cout << '\n';
    }
}

Кому интересно это решение через Дерево Фенвика!

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 5e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

ll n, k, q, a[N], t[N], b[N];

ll get(ll pos) {
    ll res = 0;
    for(ll i = pos; i >= 1; i = (i & (i + 1)) - 1) {
        res += t[i];
    }
    return res;
}

void update(ll pos, ll x) {
    for(ll i = pos; i <= k; i |= i + 1) {
        t[i] += x;
    }
}

ll sum(ll l, ll r) {
    return (get(r) - get(l - 1));
}

int main () {
    start
    cin >> n >> k;
    for(ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        a[x]++;
        b[i] = x;
        update(x, 1);
    }
    cin >> q;
    while(q--) {
        char x;
        cin >> x;
        if(x == 'L') {
            ll pos;
            cin >> pos;
            update(b[pos], -1);
            update(b[pos] - 1, 1);
            b[pos]--;
            a[b[pos]]--;
            a[b[pos] - 1]++;
        }
        if(x == 'R') {
            ll pos;
            cin >> pos;
            update(b[pos], -1);
            update(b[pos] + 1, 1);
            b[pos]++;
            a[b[pos]]--;
            a[b[pos] + 1]++;
        }
        if(x == 'G') {
            ll l, r;
            cin >> l >> r;
            cout << sum(l, r) << "\n";
        }
    }
    return 0;
}
/*

*/

показать/скрыть код

k,n = list(map(int,(input().split()))) # кролики, грядки
grydka=[str(i) for i in range(1,n+1)] # список грядок
pos=[int(i) for i in input().split()] # первоначальная позиция

def func():
    for i in range(k):
        grydka[pos[i]-1] = [i+1,str(grydka[pos[i]-1])]
func()

q=int(input()) # запросы

for q in range(q):
    count = 0
    req=input().split()
    if req[0] == "G":
        for i in range(int(req[1])-1,int(req[2])):
            if len(grydka[i]) == 2: count+=1
        print(count)
    if req[0] == "L":
        pos[int(req[1])-1] -= 1
        for i in grydka:
            if type(i) == list: grydka[grydka.index(i)] = grydka[grydka.index(i)][1]
        func()
    if req[0] == "R":
        pos[int(req[1])-1] += 1
        for i in grydka:
            if type(i) == list: grydka[grydka.index(i)] = grydka[grydka.index(i)][1]
        func()

Обычное дп

показать/скрыть код

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
using ll = long long;

#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define FOR(i, a, b) for(int i = a; i < b; i++)

int n, k, val, q, l, r;
vector<int> v, dp;

void solve() {
   char c;
   cin >> c;
   if (c == 'L') {
      cin >> val;
      dp[--v[--val]]++;
   }
   else if (c == 'R') {
      cin >> val;
      dp[v[--val]++]--;
   }
   else {
      cin >> l >> r;
      l--, r--;
      if (l == 0)
         cout << dp[r];
      else
         cout << dp[r] - dp[l - 1];
      cout << "\n";
   }
}

int main() {
   speed;

   cin >> n >> k;
   v.resize(n), dp.resize(k);
   FOR(i, 0, n) {
      cin >> v[i];
      v[i]--;
      dp[v[i]]++;
   }
   FOR(i, 1, k)
      dp[i] += dp[i - 1];
   cin >> q;
   while (q--)
      solve();

   return 0;
}

Решение на Python:

kr, gr = map(int, input().split())

sad=[]

z=0

schet=0

superschet=[]

sad=(input().split())

for i in range(len(sad)):

z=int(sad[i])

sad[i]=z

deis=input()

deis=int(deis)

for i in range(deis):

hod=input().split()

if(hod[0]=="G"):

for i in range(len(sad)):

if(sad[i]>=int(hod[1]) and sad[i]<=int(hod[2])):

schet+=1

superschet.append(schet)

schet=0

if(hod[0]=="R"):

sad[int(hod[1])-1]=sad[int(hod[1])-1]+1

if(hod[0]=="L"):

sad[int(hod[1])-1]=sad[int(hod[1])-1]-1

for i in range(len(superschet)):

print(superschet[i])

показать/скрыть код

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main(){
	int n, k, t;
	cin >> n >> k;
	int a[n];
	for(int i = 0; i<n; i++){
		cin >> a[i];
	}
	cin >> t;
	while(t--){
		char s;
		int l, r, x, ans = 0;
		cin >> s;
		if(s == 'G'){
			cin >> l >> r;
			for(int i = 0; i<n; i++){
				for(int j = l; j<=r;j++){
					if(a[i] == j) ans+=1;
				}
			}
			cout << ans << endl;
		}
		else if(s == 'R'){
			cin >> x;
			a[x-1] +=1;
		}
		else if(s == 'L'){
			cin >> x;
			a[x-1] -=1;
		}
	}
}

показать/скрыть код

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
using namespace std;
int a[1000000], arr[10000000];
int main(){
    speed;
    ll n, m;
    cin >> n >> m;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
        arr[a[i]]++;
    }
    for(ll i = 1; i <= m; i++) {
        arr[i] += arr[i - 1];
    }
    ll q;
    cin >> q;
    while(q--) {
        char res;
        cin >> res;
        if(res == 'G') {
            ll l, r;
            cin >> l >> r;
            cout << arr[r] - arr[l - 1] << "\n";
        }
        else if(res == 'L') {
            ll l;
            cin >> l;
            a[l]--;
            arr[a[l]]++;
        }
        else {
            ll r;
            cin >> r;
            a[r]++;
            arr[a[r] - 1]--;
        }
    }
}

показать/скрыть код

n, K = map(int, input().split()) # кролики, грядки
r = list(map(int, input().split())) # первоначальная позиция
q = int(input()) # запросы
count = [] # 
for i in range(q):
    p = list(map(str, input().split())) # запрос
    if p[0] == 'G':
        s = 0
        number_one = int(p[1])
        number_two = int(p[2])
        for j in r:
            if number_one <= j <= number_two:
                s += 1
        count.append(s)
    if p[0] == 'R':
        r[int(p[1])-1] += 1
    if p[0] == 'L':
        r[int(p[1])-1] -= 1

for i in count:
    print(i)

#python

n, k = map(int, input().split())

a = list(map(int, input().split()))

g = int(input())

b = [0]

l = []

for i in range(n):

b.append(a[i])

for i in range(g):

s = input().split()

w = 0

if 'G' in s:

x = int(s[1])

y = int(s[2])

for j in b:

if x <= j <= y:

w += 1

l.append(w)

if 'R' in s:

x = int(s[1])

b[x] = b[x] + 1

if 'L' in s:

x = int(s[1])

b[x] = b[x] - 1

print(*l)

Не за что)

показать/скрыть код

n, K = map(int, input().split())
lx = list(map(int, input().split()))
q = int(input())
cnts = []
for i in range(q):
    cnt = 0
    lq = list(input().split())
    if lq[0] == 'R':
        index_x = int(lq[1])-1
        lx[index_x] += 1
    elif lq[0] == 'L':
        index_x = int(lq[1])-1
        lx[index_x] -= 1
    elif lq[0] == 'G':
        for i in lx:
            if i >= int(lq[1]) and i <= int(lq[2]):
                cnt += 1
        cnts.append(cnt)

for el in cnts:
    print(el)