Submission #371073

#	Time	Username	Problem	Language	Result	Execution time	Memory
371073		Bench0310	Treasure Hunt (CEOI11_tre)	C++17	100 / 100	3508 ms	245772 KiB

Main

#include <bits/stdc++.h>
//#include "treasure.h"

using namespace std;
typedef long long ll;

const int N=2500000;
struct Node;
using twoNodes=array<Node*,2>;

struct Node
{
    int val;
    int l,r;
    int sum;
    int flip;
    twoNodes kids;
    Node *p;
    Node *pathp;
    twoNodes neighbours;
    void ini(int a,int b){val=(b-a+1);l=a;r=b;sum=val;flip=0;kids[0]=kids[1]=p=pathp=nullptr;}
}buf[N];

int buf_now=0;

Node* newNode(int a,int b)
{
    Node *t=&buf[buf_now++];
    t->ini(a,b);
    return t;
}

int side(Node *me){return (me->p?(me->p->kids[1]==me):0);}

void recalc(Node *me)
{
    if(!me) return;
    me->sum=me->val;
    for(Node *to:me->kids) if(to) me->sum+=to->sum;
}

void apply(Node *me)
{
    if(!me) return;
    swap(me->kids[0],me->kids[1]);
    me->flip^=1;
}

void prop(Node *me)
{
    if(me&&me->flip==1)
    {
        for(Node *to:me->kids) apply(to);
        me->flip=0;
    }
}

void make_parent(Node *me,int id,Node *kid)
{
    if(me) me->kids[id]=kid;
    recalc(me);
    if(kid) kid->p=me;
}

void unmake_parent(Node *me,int id)
{
    make_parent(nullptr,0,me->kids[id]);
    make_parent(me,id,nullptr);
}

void rotate_up(Node *me)
{
    Node *p=me->p;
    int id=side(me);
    if(!p->p) swap(me->pathp,p->pathp);
    make_parent(p->p,side(p),me);
    make_parent(p,id,me->kids[id^1]);
    make_parent(me,id^1,p);
}

void splay(Node *me)
{
    while(me->p)
    {
        prop(me->p->p);
        prop(me->p);
        prop(me);
        if(me->p->p)
        {
            if(side(me)==side(me->p)) rotate_up(me->p);
            else rotate_up(me);
        }
        rotate_up(me);
    }
    prop(me);
    recalc(me);
}

void detach_path(Node *me)
{
    if(me->kids[1]) me->kids[1]->pathp=me;
    unmake_parent(me,1);
}

Node* access(Node *me)
{
    Node *up=me;
    splay(me);
    detach_path(me);
    while(me->pathp)
    {
        up=me->pathp;
        me->pathp=nullptr;
        splay(up);
        detach_path(up);
        make_parent(up,1,me);
        splay(me);
    }
    return up;
}

void make_root(Node *me)
{
    access(me);
    apply(me);
}

void cut(Node *me)
{
    access(me);
    unmake_parent(me,0);
}

void link(Node *me,Node *up)
{
    access(me);
    access(up);
    make_parent(me,0,up);
}

map<int,Node*> m;
int id;

void init()
{
    m[1]=newNode(1,1);
    id=1;
}

map<int,Node*>::iterator find_it(int a)
{
    auto it=m.lower_bound(a+1);
    it--;
    return it;
}

Node* find_node(int a)
{
    return (find_it(a)->second);
}

void split(int a)
{
    auto it=find_it(a);
    Node *now=(it->second);
    int l=now->l;
    int r=now->r;
    if(l==r) return;
    Node *prv=(now->neighbours[0]);
    Node *nxt=(now->neighbours[1]);
    make_root(now);
    cut(prv);
    cut(nxt);
    auto it_pos=m.erase(it);
    vector<Node*> v={prv};
    if(l<a) v.push_back(newNode(l,a-1));
    v.push_back(newNode(a,a));
    if(a<r) v.push_back(newNode(a+1,r));
    v.push_back(nxt);
    for(int i=1;i<(int)v.size()-1;i++) m.insert(it_pos,{v[i]->l,v[i]});
    for(int i=0;i<(int)v.size()-1;i++)
    {
        make_root(v[i]);
        link(v[i],v[i+1]);
        if(i>0) v[i]->neighbours={v[i-1],v[i+1]};
    }
}

void path(int a,int s)
{
    int b=id+s;
    Node *e=newNode(b,b);
    auto it_pos=m.insert({b,e}).first;
    split(a);
    Node *node_a=find_node(a);
    if(s==1) link(e,node_a);
    else
    {
        Node *mid=newNode(id+1,b-1);
        m.insert(it_pos,{id+1,mid});
        mid->neighbours={node_a,e};
        link(mid,node_a);
        link(e,mid);
    }
    id=b;
//    cout << "after op:" << endl;
//    for(auto [x,p]:m)
//    {
//        cout << "[" << x[0] << "," << x[1] << "]: " << p << endl;
//    }
}

void pr(Node *me)
{
    if(!me) return;
    prop(me);
    pr(me->kids[0]);
    cout << "[" << me->l << "," << me->r << "] ";
    pr(me->kids[1]);
}

Node* descend(Node *me,int cnt)
{
    prop(me);
    int l=(me->kids[0]?me->kids[0]->sum:0);
    if(l>=cnt) return descend(me->kids[0],cnt);
    cnt-=l;
    if(me->val>=cnt) return me;
    cnt-=(me->val);
    return descend(me->kids[1],cnt);
}

Node* find_prv(Node *me)
{
    prop(me);
    me=me->kids[0];
    prop(me);
    while(me->kids[1])
    {
        me=me->kids[1];
        prop(me);
    }
    splay(me);
    return me;
}

int dig(int a,int b)
{
    split(a);
    split(b);
    Node *one=find_node(a);
    Node *two=find_node(b);
    make_root(one);
    access(two);
    splay(one);
//    cout << "path a->b: ";
//    pr(one);
//    cout << endl;
    int path_len=(one->sum);
    int half_len=(path_len+1)/2;
//    cout << "path_len=" << path_len << endl;
    Node *t=descend(one,half_len);
    splay(t);
    if(t->val==1) return (t->l);
    Node *prv=find_prv(t);
    int src=(prv->l);
    int here_len=(prv->val+(prv->kids[0]?prv->kids[0]->sum:0));
    splay(t);
    int kth=(half_len-here_len);
    int c=t->l;
    int d=t->r;
    if(src<c) return c+kth-1;
    else return d-kth+1;
}

//int main()
//{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    int n;
//    cin >> n;
//    while(n--)
//    {
//        char t;
//        int a,b;
//        cin >> t >> a >> b;
//        if(t=='i') init();
//        else if(t=='p') path(a,b);
//        else if(t=='d') cout << dig(a,b) << endl;
//    }
//    return 0;
//}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10