Submission #92119

#	Time	Username	Problem	Language	Result	Execution time	Memory
92119		emil_physmath	Segments (IZhO18_segments)	C++17	7 / 100	5015 ms	7804 KiB

segments

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;

void SubTaskOne(int n, int t);
void SubTaskTwo(int n, int t);
void SubTaskThree(int n, int t);
int FindAns(const multiset<int> & segL, const multiset<int> & segR, int l, int r, int k);
int main()
{
	int n, t;
	cin>>n>>t;
	if (n<=5000)
		SubTaskOne(n, t);
	else
		SubTaskThree(n, t);

	char I;
	cin >> I;
	return 0;
}

void SubTaskOne(int n, int t)
{
	int lastans=0;
	vector<pair<int, int> > seg;
	while (n--)
	{
		int type, l, r, k, id;
		cin>>type;
		if (type==1)
		{
			cin>>l>>r;
			l=(l^(t*lastans));
			r=(r^(t*lastans));
			if (l>r) swap(l, r);
			seg.push_back(make_pair(l, r));
		}
		else if (type==2)
		{
			cin>>id;
			seg[id-1]=make_pair(-1, -1);
		}
		else if (type==3)
		{
			int ans=0;
			cin>>l>>r>>k;
			l=(l^(t*lastans));
			r=(r^(t*lastans));
			if (l>r) swap(l, r);
			for (int i=0; i<seg.size(); i++)
				if (seg[i].first!=-1 && min(seg[i].second, r)-max(seg[i].first, l)+1>=k)
					ans++;
			cout<<ans<<'\n';
			lastans=ans;
		}
	}
}

void SubTaskThree(int n, int t)
{
	int lastans=0;
	vector<pair<int, int> > a;
	multiset<int> a_l, a_r;
	while (n--)
	{
		int type, l, r, k, id;
		scanf("%d", &type);
		if (type==1)
		{
			scanf("%d%d", &l, &r);
			l=(l^(t*lastans));
			r=(r^(t*lastans));
			if (l>r) swap(l, r);
			a.push_back(make_pair(l, r));
			a_l.insert(l);
			a_r.insert(r);
		}
		else if (type==2)
		{
			scanf("%d", &id);
			// b.push_back(a[id-1]);
			a_l.erase(a_l.find(a[id-1].first));
			a_r.erase(a_r.find(a[id-1].second));
		}
		else if (type==3)
		{
			int ans=0;
			scanf("%d%d%d", &l, &r, &k);
			l=(l^(t*lastans));
			r=(r^(t*lastans));
			if (l>r) swap(l, r);
			ans=FindAns(a_l, a_r, l, r, k);
			printf("%d\n", ans);
			lastans=ans;
		}
	}
}

int FindAns(const multiset<int> & segL, const multiset<int> & segR, int l, int r, int k)
{
	if (k==1)
	{
		int ans=segL.size();
		ans-=distance(segL.upper_bound(r), segL.end());
		if (segR.size())
		{
			auto it=segR.lower_bound(l);
			if (it!=segR.begin()) ans-=distance(segR.begin(), --it)+1;
		}
		return ans;
	}
}

Compilation message (stderr)

segments.cpp: In function 'void SubTaskOne(int, int)':
segments.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<seg.size(); i++)
                  ~^~~~~~~~~~~
segments.cpp: In function 'void SubTaskThree(int, int)':
segments.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &type);
   ~~~~~^~~~~~~~~~~~~
segments.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &id);
    ~~~~~^~~~~~~~~~~
segments.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &l, &r, &k);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int FindAns(const std::multiset<int>&, const std::multiset<int>&, int, int, int)':
segments.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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