QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#43011 | #4270. Double Attendance | ppavic# | 0 | 0ms | 3888kb | C++ | 1.5kb | 2022-08-05 17:29:27 | 2024-05-26 01:03:30 |
Judging History
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;
}
詳細信息
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%