QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#333661#4270. Double Attendancewhdywjd0 0ms1596kbC++144.9kb2024-02-20 11:33:362024-02-20 11:33:36

Judging History

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

  • [2024-02-20 11:33:36]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:1596kb
  • [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;
}

詳細信息

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%