QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#43011#4270. Double Attendanceppavic#0 0ms3888kbC++1.5kb2022-08-05 17:29:272024-05-26 01:03:30

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 01:03:30]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3888kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-05 17:29:27]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int , int > pii;

const int N = 3e5 + 500;
const int M = 2e6 + 500;

int n, m, k;
int dp[N][2];

vector < pii > S[2];
vector < int > v;

int gdje(int x, int tko){
	if(S[tko].back().Y < x || S[tko][0].X > x) return -1;
	int gdje = lower_bound(S[tko].begin(), S[tko].end(), (pii){x, 0}) - S[tko].begin();
	return S[tko][gdje].Y > x ? gdje : -1;
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 0;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		S[0].PB({x, y});
		v.PB(x); v.PB(y - 1);
		v.PB(max(x - k, 0));
		v.PB(max(y - k - 1, 0));
	}
	for(int i = 0;i < m;i++){
		int x, y; scanf("%d%d", &x, &y);
		S[1].PB({x, y});
		v.PB(x); v.PB(y - 1);
		v.PB(max(x - k, 0));
		v.PB(max(y - k - 1, 0));
	}
	sort(S[0].begin(), S[0].end());
	sort(S[1].begin(), S[1].end());
	v.PB(0);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	dp[0][0] = gdje(0, 0) != -1;
	dp[0][1] = -(int)1e9;
	int ans = 0;
	for(int i = 1;i < (int)v.size();i++){
		for(int tko = 0;tko < 2;tko++){
			int tren = gdje(v[i], tko);
			if(tren != -1 && tren != gdje(v[i - 1], tko))
				dp[i][tko] = dp[i - 1][tko] + 1;
			int j = upper_bound(v.begin(), v.end(), v[i] - k) - v.begin();
			if(j > 0)
				dp[i][tko] = max(dp[i][tko], 1 + dp[j - 1][!tko]);
			ans = max(ans, dp[i][tko]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3820kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

5

result:

wrong answer 1st lines differ - expected: '3', found: '5'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 0
Wrong Answer
time: 0ms
memory: 3888kb

input:

1 1 1
0 1
0 1

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%