QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43018 | #4270. Double Attendance | ppavic# | 0 | 55ms | 6992kb | C++ | 1.7kb | 2022-08-05 17:45:35 | 2024-05-26 01:03:40 |
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 = upper_bound(S[tko].begin(), S[tko].end(), (pii){x, (int)1e9 + 100}) - S[tko].begin() - 1;
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);
for(int i = 0;i < N;i++) v.PB(i);
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 = dp[0][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;
else
dp[i][tko] = dp[i - 1][tko];
int j = upper_bound(v.begin(), v.end(), v[i] - k) - v.begin();
if(j > 0)
dp[i][tko] = max(dp[i][tko], (tren != -1) + dp[j - 1][!tko]);
//printf("dp[ %d ][ %d ] = %d\n", v[i], tko, dp[i][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: 5
Accepted
time: 31ms
memory: 6812kb
input:
3 1 8 10 20 100 101 20 21 15 25
output:
3
result:
ok single line: '3'
Test #2:
score: -5
Wrong Answer
time: 27ms
memory: 6732kb
input:
1 5 3 1 100 1 2 2 3 3 4 4 5 5 6
output:
19
result:
wrong answer 1st lines differ - expected: '4', found: '19'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Runtime Error
Test #104:
score: 6
Accepted
time: 35ms
memory: 6840kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #105:
score: 0
Accepted
time: 55ms
memory: 6992kb
input:
1 2000 2 999999996 1000000000 336 337 502 503 1906 1907 963 964 1351 1352 1795 1796 1510 1511 304 305 1930 1931 1735 1736 1469 1470 338 339 813 814 182 183 209 210 321 322 849 850 721 722 394 395 889 890 1758 1759 1440 1441 560 561 1470 1471 1916 1917 793 794 1366 1367 158 159 1602 1603 214 215 1119...
output:
2000
result:
ok single line: '2000'
Test #106:
score: -6
Runtime Error
input:
2000 2000 249875 608195750 608695500 88455750 88955500 579210250 579710000 817091250 817591000 527736000 528235750 52473750 52973500 89955000 90454750 184407750 184907500 668165750 668665500 24487750 24987500 466266750 466766500 471764000 472263750 212393750 212893500 250874500 251374250 939530000 9...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%