oj.uz

Submission #828109

# Submission time Handle Problem Language Result Execution time Memory
828109 2023-08-17T05:09:59 Z 박상훈(#10381) Inspections (NOI23_inspections) C++17
0 / 100
 1 ms 312 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 1e18;

multiset<array<ll, 2>> st;
ll L[200200], R[200200], ofs[200200];
vector<array<ll, 2>> S;

void insert(int p, int t){
	auto iter = st.insert({ofs[p], t});
	auto piter = (iter==st.begin())?iter:prev(iter);
	auto niter = next(iter);

	if (iter!=st.begin() && niter!=st.end()){
		S.push_back({(*niter)[0] - (*piter)[0], t - max((*piter)[1], (*niter)[1])});
	}
}

void erase(int p, int t){
	auto iter = st.find({ofs[p], L[p]});
	auto piter = (iter==st.begin())?iter:prev(iter);
	auto niter = next(iter);

	if (iter!=st.begin()){
		S.push_back({(*iter)[0] - (*piter)[0], t - max((*piter)[1], (*iter)[1])});
	}
	if (niter!=st.end()){
		S.push_back({(*niter)[0] - (*iter)[0], t - max((*iter)[1], (*niter)[1])});
	}

	st.erase(iter);
}

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);

	vector<array<ll, 3>> E;
	ll cur = 1;

	for (int i=1;i<=m;i++){
		scanf("%lld %lld", L+i, R+i);
		E.push_back({L[i], i, 0});
		E.push_back({R[i]+1, i, 1});

		ofs[i] = -L[i] + cur;
		cur += R[i]-L[i]+1;
	}

	sort(E.begin(), E.end());
	int pt = 0;
	for (int i=1;i<=n+1;i++){
		// printf("i = %d\n", i);
		while(pt<(int)E.size() && E[pt][0]==i){
			if (E[pt][2]==0) insert(E[pt][1], i);
			else erase(E[pt][1], i);
			pt++;

			// for (auto &[x, y]:st) printf(" %lld %lld\n", x, y);
		}
	}

	S.push_back({-1, 0});
	S.push_back({INF, 0});
	sort(S.begin(), S.end());
	
	for (int i=1;i<(int)S.size();i++) S[i][1] += S[i-1][1];

	while(q--){
		ll x;
		scanf("%lld", &x);
		++x;

		auto iter = lower_bound(S.begin(), S.end(), array<ll, 2>{x, 0});
		--iter;
		ll ans = S.back()[1] - (*iter)[1];
		printf("%lld ", ans);
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%lld %lld", L+i, R+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%lld", &x);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

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

Subtask #5
0 / 23.0

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