Submission #226010

#	Time	Username	Problem	Language	Result	Execution time	Memory
226010		emil_physmath	Segments (IZhO18_segments)	C++17	100 / 100	2089 ms	12028 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 = 1450;

struct
{
    vector<int> ls[maxN / bl], rs[maxN / bl];
    vector<Inter> seg;
    vector<Inter> unProc;
    void add(int l, int r)
    {
        unProc.push_back({l, r});
        if (unProc.size() >= bl)
        {
            // Rebuild.
            vector<Inter> temp; temp.reserve(seg.size() + unProc.size());
            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 * bl < seg.size(); ++i)
            {
                ls[i].clear();
                rs[i].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);
            }
            for (int i = 0; i * bl < seg.size(); ++i)
            {
                sort(ls[i].begin(), ls[i].end());
                sort(rs[i].begin(), rs[i].end());
            }
        }
    }
    int solve(int l, int r, int k)
    {
        if (r - l + 1 < k)
            return 0;
        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 + 1 >= k)
            {
                ans += e - i + 1;
                ans -= lower_bound(rs[i / bl].begin(), rs[i / bl].end(), l + k - 1) - rs[i / bl].begin();
                ans -= ls[i / bl].end() - upper_bound(ls[i / bl].begin(), ls[i / bl].end(), r - (k - 1));
            }
            else if (seg[e].r - seg[e].l + 1 >= k)
                for (int j = i; j <= e; ++j)
                    ans += (min(seg[j].r, r) - max(seg[j].l, l) + 1 >= k);
        }
        for (auto p: unProc)
            if (min(r, p.r) - max(l, p.l) + 1 >= k)
                ++ans;
        return ans;
    }
} exist, del;

int main()
{
    int n, t;
    cin >> n >> t;
	int prevans = 0;
    vector<Inter> allSegs;
	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);
            allSegs.push_back({l, r});
			exist.add(l, r);
		}
		else if (type == 2)
		{
			cin >> id; --id;
            del.add(allSegs[id].l, allSegs[id].r);
		}
		else if (type == 3)
		{
			cin >> l >> r >> k;
			l = (l ^ (t * prevans));
			r = (r ^ (t * prevans));
			if (l > r) swap(l, r);
            cout << (prevans = exist.solve(l, r, k) - del.solve(l, r, k)) << '\n';
#ifdef MANSON
            cout << flush;
#endif
		}
	}
}

Compilation message (stderr)

segments.cpp: In member function 'void<unnamed struct>::add(int, int)':
segments.cpp:29:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i * bl < seg.size(); ++i)
                             ~~~~~~~^~~~~~~~~~~~
segments.cpp:34:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < seg.size(); ++i)
                             ~~^~~~~~~~~~~~
segments.cpp:39:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i * bl < seg.size(); ++i)
                             ~~~~~~~^~~~~~~~~~~~
segments.cpp: In member function 'int<unnamed struct>::solve(int, int, int)':
segments.cpp:51:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < seg.size(); i += bl)
                         ~~^~~~~~~~~~~~

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