QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333661 | #4270. Double Attendance | whdywjd | 0 | 0ms | 1596kb | C++14 | 4.9kb | 2024-02-20 11:33:36 | 2024-02-20 11:33:36 |
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#define ll long long
#define _mp make_pair
#define _pb push_back
#define _1 first
#define _2 second
#define MAX_N 2222222
#define inf 2222222222222222222ll
#define Assert(X) if(!(X)) printf("ERROR ON LINE %d.\n", __LINE__), exit(0)
using namespace std;
ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}
char gtc(){char c = 0;while(c < 33)c = getchar();return c;}
int n, m;
ll k;
pair<ll, ll> ta[MAX_N], tb[MAX_N];
inline int nxtid(int id) { return id < 0 ? -id : id + 1; }
inline ll nxtna(int id)
{
id = nxtid(id);
if(id > n)
return inf;
Assert(id >= 1 && id <= n);
return ta[id]._1;
}
inline ll nxtnb(int id)
{
id = nxtid(id);
if(id > m)
return inf;
Assert(id >= 1 && id <= m);
return tb[id]._1;
}
int geta(ll t)
{
if(t < ta[1]._1)
return -1;
int l = 1, r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(ta[mid]._1 <= t)
l = mid;
else
r = mid - 1;
}
if(ta[l]._2 >= t)
return l;
return -(l + 1);
}
int getb(ll t)
{
if(t < tb[1]._1)
return -1;
int l = 1, r = m;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(tb[mid]._1 <= t)
l = mid;
else
r = mid - 1;
}
if(tb[l]._2 >= t)
return l;
return -(l + 1);
}
ll a[MAX_N], b[MAX_N];
int fa[MAX_N], fb[MAX_N], pa[MAX_N], pb[MAX_N];
struct node
{
ll nxt;
int p;
node() { ; }
node(ll _nxt, int _p) : nxt(_nxt), p(_p) { ; }
};
bool operator < (node a, node b) { return _mp(a.nxt, a.p) < _mp(b.nxt, b.p); }
void operator += (node& a, node b)
{
if(b < a)
a = b;
}
void MAIN()
{
n = read();
m = read();
k = read();
for(int i = 1; i <= n; i++)
ta[i]._1 = read(), ta[i]._2 = read();
for(int i = 1; i <= m; i++)
tb[i]._1 = read(), tb[i]._2 = read();
sort(ta + 1, ta + n + 1);
sort(tb + 1, tb + m + 1);
a[0] = 1;
pa[0] = geta(1);
b[0] = k + 1;
pb[0] = getb(k + 1);
fa[0] = fb[0] = -1;
int ca = 0, cb = 0;
if(pa[0] > 0)
a[1] = a[0], pa[1] = pa[0], fa[1] = fa[0], ca = 1;
if(pb[0] > 0)
b[1] = b[0], pb[1] = pb[0], fb[1] = fb[0], cb = 1;
while(1)
{
node na = node(nxtna(pa[ca]), fa[ca]);
node nb = node(nxtnb(pb[cb]), fb[cb]);
//printf(": %lld %lld\n", na.nxt, nb.nxt);
if(cb > ca)
na += node(b[ca + 1] + k, pb[ca + 1]);
if(ca > cb)
nb += node(a[cb + 1] + k, pa[cb + 1]);
if(cb >= ca)
{
int pos = geta(b[ca] + k);
if(pos > 0 && pos != fb[ca])
na += node(b[ca] + k, pb[ca]);
else
{
if(pos < 0)
pos = -pos;
if(pos == fb[ca])
pos++;
if(pos <= n)
{
if(pb[ca] != getb(ta[pos]._1 - k))
na += node(ta[pos]._1, -1);
else
na += node(ta[pos]._1, pb[ca]);
}
}
}
if(ca >= cb)
{
int pos = getb(a[cb] + k);
if(pos > 0 && pos != fa[cb])
nb += node(a[cb] + k, pa[cb]);
else
{
if(pos < 0)
pos = -pos;
if(pos == fa[cb])
pos++;
if(pos <= m)
{
if(pa[cb] != geta(tb[pos]._1 - k))
nb += node(tb[pos]._1, -1);
else
nb += node(tb[pos]._1, pa[cb]);
}
}
}
if(na.nxt == inf && nb.nxt == inf)
break;
if(na.nxt <= nb.nxt)
a[++ca] = na.nxt, pa[ca] = geta(a[ca]), fa[ca] = na.p;
if(nb.nxt <= na.nxt)
b[++cb] = nb.nxt, pb[cb] = getb(b[cb]), fb[cb] = nb.p;
Assert(ca <= n + m && cb <= n + m);
//printf("%d %d\n", ca, cb);
}
/*printf("\n");
for(int i = 0; i <= 4; i++)
printf("%lld %d %d\n", a[i], pa[i], fa[i]);
printf("\n");
for(int i = 0; i <= 4; i++)
printf("%lld %d %d\n", b[i], pb[i], fb[i]);
printf("\n");*/
printf("%d\n", max(ca, cb));
}
void CLEAR()
{
;
}
void EXP()
{
;
}
int main()
{
EXP();
int T = 1;
while(T--)
MAIN(), CLEAR();
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: 0ms
memory: 1540kb
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: 0ms
memory: 1496kb
input:
1 5 3 1 100 1 2 2 3 3 4 4 5 5 6
output:
3
result:
wrong answer 1st lines differ - expected: '4', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #104:
score: 6
Accepted
time: 0ms
memory: 1548kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #105:
score: -6
Wrong Answer
time: 0ms
memory: 1596kb
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:
1999
result:
wrong answer 1st lines differ - expected: '2000', found: '1999'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%