Submission #92116

#	Time	Username	Problem	Language	Result	Execution time	Memory
92116		emil_physmath	Segments (IZhO18_segments)	C++17	7 / 100	101 ms	6436 KiB

segments

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

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

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

void SubTaskOne(long long n, long long t)
{
	long long lastans=0;
	vector<pair<long long, long long> > seg;
	while (n--)
	{
		long long 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)
		{
			long long ans=0;
			cin>>l>>r>>k;
			l=(l^(t*lastans));
			r=(r^(t*lastans));
			if (l>r) swap(l, r);
			for (long long 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(long long n, long long t)
{
	long long lastans=0;
	vector<pair<long long, long long> > a;
	multiset<long long> a_l, a_r;
	while (n--)
	{
		long long type, l, r, k, id;
		scanf("%lld", &type);
		if (type==1)
		{
			scanf("%lld%lld", &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("%lld", &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)
		{
			long long ans=0;
			scanf("%lld%lld%lld", &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("%lld\n", ans);
			lastans=ans;
		}
	}
}

long long FindAns(const multiset<long long> & segL, const multiset<long long> & segR, long long l, long long r, long long k)
{
	if (k==1)
	{
		long long 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);
		}
		return ans;
	}
}

Compilation message (stderr)

segments.cpp: In function 'void SubTaskOne(long long int, long long int)':
segments.cpp:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (long long i=0; i<seg.size(); i++)
                        ~^~~~~~~~~~~
segments.cpp: In function 'void SubTaskThree(long long int, long long int)':
segments.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &type);
   ~~~~~^~~~~~~~~~~~~~~
segments.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &id);
    ~~~~~^~~~~~~~~~~~~
segments.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld", &l, &r, &k);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'long long int FindAns(const std::multiset<long long int>&, const std::multiset<long long int>&, long long int, long long int, long long 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