Submission #1171651

#TimeUsernameProblemLanguageResultExecution timeMemory
1171651HanksburgerGame (IOI13_game)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
using namespace std;
int n, cnt1, cnt2, mod=30013;
pair<int, int> combine(pair<int, int> x, pair<int, int> y)
{
    if (x.first!=y.first)
        return x.first>y.first?x:y;
    return {x.first, (x.second+y.second)%mod};
}
struct node2
{
    pair<int, int> val;
    node2 *lc, *rc;
    int l, r;
    node2(int l, int r) : val({0, 0}), lc(0), rc(0), l(l), r(r) {}
};
struct node1
{
    node1 *lc, *rc;
    node2 *x;
    node1() : lc(0), rc(0), x(0) {}
};
void update2(node2 *i, int y, pair<int, int> z)
{
    if (i->l==i->r)
    {
        i->val=z;
        return;
    }
    int mid=(i->l+i->r)/2;
    if (y<=mid)
    {
        if (!i->lc)
            i->lc=new node2(y, y);
        else if (y<i->lc->l || y>i->lc->r)
        {
            int l=i->l, r=i->r, m=(l+r)/2;
            while ((y<=m)^(i->lc->l>m))
            {
                if (y<=m)
                    r=m;
                else
                    l=m+1;
                m=(l+r)/2;
            }
            node2 *j=new node2(l, r);
            if (y<=m)
                j->rc=i->lc;
            else
                j->lc=i->lc;
            i->lc=j;
        }
        update2(i->lc, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node2(y, y);
        else if (y<i->rc->l || y>i->rc->r)
        {
            int l=i->l, r=i->r, m=(l+r)/2;
            while ((y<=m)^(i->rc->l>m))
            {
                if (y<=m)
                    r=m;
                else
                    l=m+1;
                m=(l+r)/2;
            }
            node2 *j=new node2(l, r);
            if (y<=m)
                j->rc=i->rc;
            else
                j->lc=i->rc;
            i->rc=j;
        }
        update2(i->rc, y, z);
    }
    i->val=combine(i->lc?i->lc->val:make_pair(0, 0), i->rc?i->rc->val:make_pair(0, 0));
}
pair<int, int> query2(node2 *i, int ql, int qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    int mid=(i->l+i->r)/2;
    pair<int, int> res={0, 0};
    if (i->l<=qr && ql<=mid && i->lc)
        res=combine(res, query2(i->lc, ql, qr));
    if (mid<qr && ql<=i->r && i->rc)
        res=combine(res, query2(i->rc, ql, qr));
    return res;
}
void update1(node1 *i, int L, int R, int x, int y, pair<int, int> z)
{
    if (L==R)
    {
        if (!i->x)
            i->x=new node2(1, cnt2);
        update2(i->x, y, z);
        return;
    }
    int mid=(L+R)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node1();
        update1(i->lc, L, mid, x, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node1();
        update1(i->rc, mid+1, R, x, y, z);
    }
    if (!i->x)
        i->x=new node2(1, cnt2);
    update2(i->x, y, combine(i->lc?query2(i->lc->x, y, y):make_pair(0, 0), i->rc?query2(i->rc->x, y, y):make_pair(0, 0)));
}
pair<int, int> query1(node1 *i, int L, int R, int ql1, int qr1, int ql2, int qr2)
{
    if (ql1<=L && R<=qr1)
        return query2(i->x, ql2, qr2);
    int mid=(L+R)/2;
    pair<int, int> res={0, 0};
    if (L<=qr1 && ql1<=mid && i->lc)
        res=combine(res, query1(i->lc, L, mid, ql1, qr1, ql2, qr2));
    if (mid<qr1 && ql1<=R && i->rc)
        res=combine(res, query1(i->rc, mid+1, R, ql1, qr1, ql2, qr2));
    return res;
}
vector<pair<pair<int, int>, pair<int, int> > > vec;
node1 *root=new node1();
map<int, int> mp1, mp2;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    mp1[0]=mp2[0]=1;
    for (int i=0; i<n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vec.push_back({{a, b}, {c, d}});
        mp1[a]=mp1[b]=mp2[c]=mp2[d]=1;
    }
    sort(vec.begin(), vec.end());
    for (auto it=mp1.begin(); it!=mp1.end(); it++)
        it->second=(++cnt1);
    for (auto it=mp2.begin(); it!=mp2.end(); it++)
        it->second=(++cnt2);
    update1(root, 1, cnt1, 1, 1, {0, 1});
    for (int i=0; i<n; i++)
    {
        pair<int, int> res=query1(root, 1, cnt1, 1, mp1[vec[i].first.first]-1, 1, mp2[vec[i].second.first]-1);
        res.first++;
        update1(root, 1, cnt1, mp1[vec[i].first.second], mp2[vec[i].second.second], res);
    }
    pair<int, int> ans=query1(root, 1, cnt1, 1, cnt1, 1, cnt2);
    cout << ans.first << ' ' << ans.second;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccwKSOdY.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cco2HOdk.o:game.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccwKSOdY.o: in function `main':
grader.c:(.text.startup+0x6a): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xcc): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x136): undefined reference to `update'
collect2: error: ld returned 1 exit status