oj.uz

Submission #226001

# Submission time Handle Problem Language Result Execution time Memory
226001 2020-04-22T09:33:37 Z emil_physmath Segments (IZhO18_segments) C++17
0 / 100
 5000 ms 14732 KB 
#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 = 2; // 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[i].l + 1 >= k)
            {
                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;
        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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Incorrect 70 ms 10104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5054 ms 12168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5071 ms 14732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 13108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Incorrect 70 ms 10104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Incorrect 70 ms 10104 KB Output isn't correct
4 Halted 0 ms 0 KB -