oj.uz

Submission #915970

# Submission time Handle Problem Language Result Execution time Memory
915970 2024-01-25T04:23:24 Z pan Inspections (NOI23_inspections) C++17
0 / 100
 239 ms 16248 KB 
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;

ll n, m, q, l, r, t;
set<pi> s;
vector<ll> last;
vector<ll> ans;
vector<pi> works;
vector<pi> queries;
vector<ll> answer;

int main()
{
	t = 0;
	cin >> n >> m >> q;
	last.assign(n+5, -1);
	ans.assign(q+5,0);
	works.resize(m+5);
	answer.resize(q);
	queries.resize(q);
	s.insert(mp(1, n));;
	for (ll i=0; i<m; ++i) cin >> works[i].f >> works[i].s;
	for (ll i=0; i<q; ++i) {cin >> queries[i].f; queries[i].s = i;}
	sort(queries.begin(), queries.end());
	for (ll i=0; i<m; ++i)
	{
		
		ll midx = LLONG_MAX, midy = LLONG_MIN;
		vector<pi> toadd;
		ll l = works[i].f, r=  works[i].s;
		ll time = t+1-l;
		auto it = s.ub(mp(l, n+1));
		it--;
		//show2(l, r);
		while (it!=s.end() && !(((*it).s<l) || (*it).f>r))
		{
			ll x = (*it).f, y= (*it).s;
			//show2(x, y);
			ll range = min(y, r)-max(x, l)+1;
			ll bound = (t+1-l) - last[x];
			//show2(range, bound);
			auto add = ub(queries.begin(), queries.end(), mp(bound, 0LL))-queries.begin();
			if (last[x]!=-1)
			{
				ans[0]+=range;
				ans[add]-=range;
			}
			if (x<l && y>r)
			{
				toadd.pb(mp(x, l-1));
				toadd.pb(mp(r+1, y));
				toadd.pb(mp(l, r));
				last[r+1] = last[x];
				last[l] = time;
			}
			else if (x>=l && y<=r) // complete 
			{
				midx = min(midx, x);
				midy = max(midy, y);
			}
			else if (x<l)
			{
				toadd.pb(mp(x, l-1));
				toadd.pb(mp(l, y));
				last[l] = time;
			}
			else if (y>r)
			{
				toadd.pb(mp(x, r));
				toadd.pb(mp(r+1, y));
				last[r+1] = last[x];
				last[x] = time;
			}
			it = s.erase(it);
		}
		for (pi u: toadd) { s.insert(u);}
		if (midx!=LLONG_MAX && midy!=LLONG_MAX)
		{
			s.insert(mp(midx, midy));
			//show2(midx, midy);
			last[midx] = time;
		}
		//for (auto x = s.begin(); x!=s.end(); ++x) show2(x->f, x->s);
		t+=r-l+1;
	}
	for (ll i=0; i<q; ++i) 
	{
		if (i) ans[i]+=ans[i-1];
		answer[queries[i].s]=ans[i];
	}
	for (ll i=0; i<q; ++i) cout << answer[i] << ' ';
		
	
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 76 ms 8656 KB Output is correct
4 Correct 87 ms 10844 KB Output is correct
5 Correct 239 ms 16248 KB Output is correct
6 Correct 218 ms 16068 KB Output is correct
7 Incorrect 163 ms 14540 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -