Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- //#include "optimization.h"
- using std::cin;
- using std::cout;
- using std::pair;
- using std::make_pair;
- using std::string;
- template<typename T>
- class seg_tree_down {
- public:
- enum color {WHITE, BLACK};
- seg_tree_down(size_t size) {
- size_t nN;
- for (nN = 1; nN <= size; nN *= 2);
- if (nN < size)
- nN *= 2;
- N_ = nN;
- delta_ = nN - size;
- //cout << "d = " << delta_ << "\n" << "N = " << N_ << "\n";
- sum_ = new T[nN * 2];
- cl_ = new color[nN * 2];
- cr_ = new color[nN * 2];
- nsegs_ = new T[nN * 2];
- for (size_t i = 0; i < nN * 2; i++) {
- sum_[i] = 0;
- cl_[i] = WHITE;
- cr_[i] = WHITE;
- nsegs_[i] = 0;
- }
- }
- void paint(color clr, size_t left, size_t right) {
- left += (N_ + delta_);
- right += (N_ + delta_);
- //cout << "left = " << left << "\nright = " << right << "\n";
- rpaint(clr, 1, 1, 2 * N_, left, right);
- }
- T nuber_of_segs() {
- return nsegs_[1];
- }
- T len() {
- return sum_[1];
- }
- private:
- void rpaint(color clr, size_t v, size_t vl, size_t vr, size_t l, size_t r, string tab = "") {
- //cout << tab << "[" << vl << ", " << vr << ")\n";
- if (l >= vr || r <= vl)
- return;
- if (l <= vl && vr <= r) {
- if (clr == BLACK) {
- sum_[v] = vr - vl;
- nsegs_[v] = 1;
- } else {
- sum_[v] = 0;
- nsegs_[v] = 0;
- }
- cl_[v] = clr;
- cr_[v] = clr;
- //cout << tab << "_LEFT is " << ((cl_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
- //cout << tab << "_RIGHT is " << ((cr_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
- //cout << tab << "_LENGHT = " << sum_[v] << "\n";
- //cout << tab << "_BS = " << nsegs_[v] << '\n';
- return;
- }
- rpaint(clr, v * 2, vl, vl + (vr - vl) / 2, l, r, tab + " ");
- rpaint(clr, v * 2 + 1, vl + (vr - vl) / 2, vr, l, r, tab + " ");
- cl_[v] = cl_[v * 2];
- cr_[v] = cr_[v * 2 + 1];
- nsegs_[v] = nsegs_[v * 2] + nsegs_[v * 2 + 1] - (cr_[v * 2] == BLACK && cl_[v * 2 + 1] == BLACK);
- sum_[v] = sum_[v * 2] + sum_[v * 2 + 1];
- // cout << tab << "LEFT is " << ((cl_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
- // cout << tab << "RIGHT is " << ((cr_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
- // cout << tab << "LENGHT = " << sum_[v] << "\n";
- // cout << tab << "BS = " << nsegs_[v] << '\n';
- }
- private:
- T *sum_;
- T *nsegs_;
- color *cl_;
- color *cr_;
- size_t N_;
- size_t delta_;
- };
- int main() {
- int N;
- cin >> N;
- seg_tree_down<size_t> line(10000);
- char ch;
- int left, lenght;
- for (int i = 0; i < N; i++) {
- cin >> ch >> left >> lenght;
- left++;
- if (ch == 'W') {
- line.paint(seg_tree_down<size_t>::WHITE, left, left + lenght);
- cout << line.nuber_of_segs() << ' ' << line.len() << '\n';
- } else if (ch == 'B') {
- line.paint(seg_tree_down<size_t>::BLACK, left, left + lenght);
- cout << line.nuber_of_segs() << ' ' << line.len() << '\n';
- } else {
- cout << "KEK\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement