Submission #225976

#	Time	Username	Problem	Language	Result	Execution time	Memory
225976		emil_physmath	Segments (IZhO18_segments)	C++17	0 / 100	748 ms	15480 KiB

segments

#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
struct Inter { int l, r; };
bool operator<(const Inter& a, const Inter& b) { return a.r - a.l < b.r - b.l; }
const int maxN = 200'000;
const int bl = 800;

vector<int> ls[maxN / bl], rs[maxN / bl];

int main()
{
    int n, t;
    cin >> n >> t;
	int prevans = 0;
	vector<Inter> seg;
    vector<Inter> unProc;
    vector<int> unProcDel;
    int deleted = 0;
	while (n--)
	{
		int type, l, r, k, id;
		cin >> type;
		if (type == 1)
		{
			cin >> l >> r;
			l = (l ^ (t * prevans));
			r = (r ^ (t * prevans));
			if (l > r) swap(l, r);
			unProc.push_back({l, r});
            if (unProc.size() + unProcDel.size() >= bl)
            {
                // Rebuild.
                vector<Inter> temp; temp.reserve(seg.size() + unProc.size() - unProcDel.size());
                for (int i: unProcDel)
                    seg[i] = {-1, -1};
                unProcDel.clear();
                deleted += unProcDel.size();
                for (int i = 0; i < seg.size(); ++i)
                    if (seg[i].l != -1)
                        temp.push_back(seg[i]);
                seg.swap(temp); temp.clear();
                sort(unProc.begin(), unProc.end());
                merge(unProc.begin(), unProc.end(), seg.begin(), seg.end(), back_inserter(temp));
                seg.swap(temp);
                unProc.clear();
                for (int i = 0; i < seg.size(); ++i)
                {
                    ls[i / bl].push_back(seg[i].l);
                    rs[i / bl].push_back(seg[i].r);
                }
            }
		}
		else if (type == 2)
		{
			cin >> id; --id;
			id -= deleted;
            unProcDel.push_back(id);
		}
		else if (type == 3)
		{
			cin >> l >> r >> k;
			l = (l ^ (t * prevans));
			r = (r ^ (t * prevans));
			if (l > r) swap(l, r);
			int ans = 0;
            for (int i = 0; i < seg.size(); i += bl)
            {
                int e = min(i + bl - 1, (int)seg.size() - 1);
                if (seg[i].r - seg[i].l >= k - 1)
                {
                    ans += e - i + 1;
                    ans -= lower_bound(ls[i / bl].begin(), ls[i / bl].end(), l + k - 1) - ls[i / bl].begin();
                    ans -= rs[i / bl].end() - upper_bound(rs[i / bl].begin(), rs[i / bl].end(), r - (k - 1));
                }
                else if (seg[e].r - seg[i].l >= k - 1)
                {
                    while (min(seg[e].r, r) - max(seg[e].l, l) + 1 >= k)
                    {
                        ++ans;
                        --e;
                    }
                }
            }
            for (auto p: unProc)
                if (min(r, p.r) - max(l, p.l) + 1 >= k)
                    ++ans;
            for (int i: unProcDel)
            {
                Inter p = (i < seg.size() ? seg[i] : unProc[i - seg.size()]);
				if (min(p.r, r) - max(p.l, l) + 1 >= k)
					--ans;
            }
            /*for (auto p: seg)
                if (p.first != -1 && p.second - p.first < k - 1)
                    --ans;
            for (auto p: seg)
                if (p.first != -1 && p.second - p.first >= k - 1 && p.second < l + k - 1)
                    --ans;
            for (auto p: seg)
                if (p.first != -1 && p.second - p.first >= k - 1 && r - (k - 1) < p.first)
                    --ans;*/
			cout << ans << '\n';
#ifdef MANSON
            cout << flush;
#endif // MANSON
			prevans = ans;
		}
	}
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:43:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < seg.size(); ++i)
                                 ~~^~~~~~~~~~~~
segments.cpp:51:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < seg.size(); ++i)
                                 ~~^~~~~~~~~~~~
segments.cpp:71:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < seg.size(); i += bl)
                             ~~^~~~~~~~~~~~
segments.cpp:94:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 Inter p = (i < seg.size() ? seg[i] : unProc[i - seg.size()]);
                            ~~^~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25