Editorial for Tetris
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Editorialist:
This question was used for the sixth PCS Standard Contest.
20 points: \(1\leq{n, s, e, i}\leq100\)
This sub-problems has small enough bounds that we can brute force an answer without too much difficulty. If we hold the number blocks in each column in an array, and update each array point one by one, our worst case complexity is \(O(T\times{n}\times{(e-s)}) = O(T\times{n^2})\), low enough to fit through our target time.
80 points: \(1\leq{n, s, e, i}\leq{5\times10^5}\)
Alas, we no longer fit in for our target time complexity. The eagle eyed among you will have spotted "range" and "point" in the question. It sounds suspiciously like some sort of reversed segment tree.
Well spoiler alert: it is!
If you take an implementation of a segment tree, change the names of the modify() and query() functions and chuck a little bit of glue on it all, you get the correct solution! The time complexity is now \(O(T\times{n}\times{log(n)})\), and we fit through our target time!
#include <bits/stdc++.h>
using namespace std;
const int N = 5*1e6; // limit for array size
int n = 5*1e6; // array size
int t[2 * N];
void modify(int l, int r, int value) {
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) t[l++] += value;
if (r&1) t[--r] += value;
}
}
int query(int p) {
int res = 0;
for (p += n; p != 0; p >>= 1) {
res += t[p];
}
return res;
}
int main() {
memset(t, 0, 2*N); // just in case
int N;
cin >> N;
char c;
for (int i = 0; i < N; ++i) {
cin >> c;
switch (c) {
case 'D':
int s, e, r;
cin >> s >> e >> r;
modify(s, e+1, r);
break;
case 'C':
int i;
cin >> i;
cout << query(i) << "\n";
break;
default:
cout << "Error! unknown case\n" << i << " " << c << "\n";
break;
}
}
}
Comments