Submission #713434

#	Time	Username	Problem	Language	Result	Execution time	Memory
713434		Vu_CG_Coder	Tram (CEOI13_tram)	C++14	70 / 100	740 ms	23860 KiB

tram

/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du    */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
    if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
    if (res > val) { res = val; return true; } return false; }

typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 30300;


struct node
{
    ll dis , x , y , l , r;
    node(){}
    node(int dis , int x , int y , int l , int r): dis(dis), x(x), y(y), l(l), r(r) {}

    bool operator < (const node k) const
    {
        if (dis == k.dis)  return C(x,y) > C(k.x,k.y);
        return dis < k.dis;
    }
};

set <int> p;
set <ii> t;
int f[200100][2];
map <ii,ii> k;
vector <node> xl;
int n , m;


iii max2(iii x , iii y)
{
    if (x.fi == y.fi) 
    {
        if (x.se < y.se) return x;
        return y;
    }
    return max(x,y);
}

iii find(int x , int y)
{
    if (x == 0 && y == n + 1) return C(n*n + 1,C(1,0));
    if (x == 0) 
    {
        if (!f[y][0]) return  C((y - 1)*(y - 1) + 1,C(1,0));
        if (!f[y][1]) return  C((y - 1)*(y - 1) + 1,C(1,1));

        if (!f[1][0])
        return  C((y - 1)*(y - 1),C(1,0));
        else return  C((y - 1)*(y - 1),C(1,1));
    }

    if (y == n + 1)
    {
        if (!f[x][0]) return  C((n - x)*(n - x) + 1,C(n,0));
        if (!f[x][1]) return  C((n - x)*(n - x) + 1,C(n,1));

        if (!f[n][0])
        return  C((n - x)*(n - x),C(n,0));
        else return  C((n - x)*(n - x),C(n,1));
    }

    ll k = (x + y);

    ll z = k/2;

    iii res = C(0,C(0,0));

    if (!f[z][0]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][0] == 0),C(z,0ll)),C(1ll*(y - z)*(y - z) + (f[y][0] == 0),C(z,0ll))));
    if (!f[z][1]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][1] == 0),C(z,1ll)),C(1ll*(y - z)*(y - z) + (f[y][1] == 0),C(z,1ll))));

    z = k/2 + 1;

    if (z <= y)
    {
        if (!f[z][0]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][0] == 0),C(z,0ll)),C(1ll*(y - z)*(y - z) + (f[y][0] == 0),C(z,0ll))));
        if (!f[z][1]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][1] == 0),C(z,1ll)),C(1ll*(y - z)*(y - z) + (f[y][1] == 0),C(z,1ll))));
    }

    z = k/2 - 1;

    if (z >= x)
    {
        if (!f[z][0]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][0] == 0),C(z,0ll)),C(1ll*(y - z)*(y - z) + (f[y][0] == 0),C(z,0ll))));
        if (!f[z][1]) res = max2(res,min(C(1ll*(z - x)*(z - x) + (f[x][1] == 0),C(z,1ll)),C(1ll*(y - z)*(y - z) + (f[y][1] == 0),C(z,1ll))));
    }

    return res;
}

set <ii> a;
set <node> b;
set <node> T[150100];
ii T2[N];
ii per[N];

void input()
{
    cin >> n >> m;
}

void solve()
{
    a.insert(C(0,0));
    a.insert(C(n + 1,0));
    b.insert(node(n,1,0,0,n + 1));
    p.insert(0);
    p.insert(n + 1);
    int cnt = 0;
    while (m--)
    {
        cnt++;
        char v;
        cin >> v;

        if (v == 'E')
        {
            auto d = b.end();
            d--;

            int x = (*d).x;
            int y = (*d).y;
            f[x][y] = 1;
            a.insert(C(x,y));
            per[cnt] = C(x,y);

            cout << x << " " << y + 1 << "\n";

            p.erase(x);
            auto l = p.lower_bound(x);
            auto r = l;
            l--;
            iii X = find(*l,x);
            iii Y = find(x,*r);

            b.insert(node(X.fi,X.two,X.thr,(*d).l,x));
            b.insert(node(Y.fi,Y.two,Y.thr,x,(*d).r));

            T[(*d).l].insert(node(X.fi,X.two,X.thr,(*d).l,x));
            T[(*d).x].insert(node(X.fi,X.two,X.thr,(*d).l,x));

            T[(*d).x].insert(node(Y.fi,Y.two,Y.thr,x,(*d).r));
            T[(*d).r].insert(node(Y.fi,Y.two,Y.thr,x,(*d).r));

            b.erase(d);
            p.insert(x);
        }
        else 
        {
            int x;
            cin >> x;

            int A = per[x].fi;
            int B = per[x].se;
            a.erase(per[x]);
            if (!(f[per[x].fi][per[x].se]^1))  p.erase(per[x].fi);

            auto l = a.lower_bound(per[x]);
            auto r = l;
            l--;
            
            for (node v : T[A]) 
            {
                b.erase(v);
                if (v.l == A && v.r == A) xl.push_back(v);
                else
                {
                    if (v.l == A) T[v.r].erase(v);
                    else T[v.l].erase(v);
                }
            }

        //    cout << (*l).fi << " - " << (*r).fi << "\n";

            T[A].clear();

            f[per[x].fi][per[x].se] = 0;

            iii K = find((*l).first,(*r).first);
            b.insert(node(K.fi,K.two,K.thr,(*l).first,(*r).first));
    
            T[(*l).first].insert(node(K.fi,K.two,K.thr,(*l).first,(*r).first));
            T[(*r).first].insert(node(K.fi,K.two,K.thr,(*l).first,(*r).first));
        }
    }

}

void solve2()
{
    a.insert(C(0,0));
    a.insert(C(n + 1,0));
    int cnt = 0;
    while (m--)
    {
        cnt++;
        char v;
        cin >> v;

        if (v == 'E')
        {
            iii res = C(0,C(0,0));

            for (auto d = a.begin() ; d != a.end() ; d++)
            {
                auto k = ++d;
                d--;
                if (k == a.end()) break;

         //       if (cnt == 6) cout << (*d).fi << " " <<(*d).se << "\n";
               // cout << (*d).fi << " " << (*k).fi << "\n";
                res = max2(res,find((*d).fi,(*k).fi));
            }

            f[res.two][res.thr] = 1;

          //  cout << find(1,4).fi;
            cout << res.two << " " << res.thr + 1 << "\n";

            T2[cnt] = C(res.two,res.thr);
            a.insert(C(res.two,res.thr));
        }
        else 
        {
            int x;
            cin >> x;

            int X = T2[x].fi;
            int Y = T2[x].se;

            a.erase(C(X,Y));
            f[X][Y] = 0;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    if(fopen(TASK".inp", "r")){
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    }

    int tk;
    tk = 1;
   //cin >> tk;
    while (tk--)
    {
        input();
        if (n >= 15000 && m >= 30000)
        solve();else solve2();
    }
    return 0;
}

Compilation message (stderr)

tram.cpp: In function 'void solve()':
tram.cpp:175:17: warning: unused variable 'B' [-Wunused-variable]
  175 |             int B = per[x].se;
      |                 ^
tram.cpp: In function 'int main()':
tram.cpp:262:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |     freopen(TASK".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tram.cpp:263:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |     freopen(TASK".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20