Submission #681077

#	Time	Username	Problem	Language	Result	Execution time	Memory
681077		Cross_Ratio	Tram (CEOI13_tram)	C++14	100 / 100	592 ms	17740 KiB

tram

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int A[150005][4];
array<int, 2> B[30005];
set<int> S;
int dis(int a, int b, int c, int d) {
    if(A[a][b]) return 0;
    if(A[c][d]==0) return INF;
    return (a-c)*(a-c)+(b-d)*(b-d);
}
int ma = -1, ix = -1, iy = -1;
void calc(int a, int b, int c) {
    if(ma<a) {
        ma = a, ix = b, iy = c;
    }
    else if(ma==a&&b<ix) {
        ix = b, iy = c;
    }
    else if(ma==a&&b==ix&&c<iy) {
        iy = c;
    }
}
int dist[150005][4];
set<array<int, 3>> S2;
int get_dis(int a, int b) {
    int d = INF;
    if(A[a][b]) d = min(d, 0LL);
    if(A[a-1][b]||A[a+1][b]||A[a][b-1]||A[a][b+1]) d = min(d, 1LL);
    if(!S.empty()) {
        auto it = S.lower_bound(a);
        if(it != S.end()) {
            d = min(d, dis(a, b, *it, 1));
            d = min(d, dis(a, b, *it, 2));
        }
        if(it != S.begin()) {
            it--;
            d = min(d, dis(a, b, *it, 1));
            d = min(d, dis(a, b, *it, 2));
        }
    }
    return d;
}
void recalc(int a, int b) {
    S2.erase({-dist[a][b], a, b});
    dist[a][b] = get_dis(a, b);
    //cout << "Recalced : " << a << ' ' << b << " , " << dist[a][b] << '\n';
    S2.insert({-dist[a][b], a, b});
}
void del(int a, int b) {
    S2.erase({-dist[a][b], a, b});
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=0;i<M;i++) B[i] = {-1,-1};
    for(j=0;j<M;j++) {
        string s1;
        cin >> s1;
        if(s1=="E") {
            ma = -1, ix = -1, iy = -1;
            if(S.empty()) {
                B[j] = {1, 1};
                cout << B[j][0] << ' ' << B[j][1] << '\n';
                A[1][1] = 1;
                S.insert(1);
                continue;
            }
          if(N <= 1500) {
            for(i=1;i<=N;i++) {
                for(int k = 1; k <= 2;k++) {
                    if(A[i][k]==0) {
                        calc(get_dis(i, k), i, k);
                    }
                }
            }
            cout << ix << ' ' << iy << '\n';
            A[ix][iy] = 1;
            B[j] = {ix, iy};
            S.insert(ix);
            continue;
          }
            //cout << "Current S : ";
            //for(int n : S) cout << n << ' ';
            //cout << '\n';
            for(i=1;i<=2;i++) {
                if(A[1][i]==0) {
                    int d = INF;
                    int k = *S.begin();
                    d = min(d, dis(1, i, k, 1));
                    d = min(d, dis(1, i, k, 2));
                    calc(d, 1, i);
                }
            }
            for(i=1;i<=2;i++) {
                if(A[N][i]==0) {
                    int d = INF;
                    int k = *S.rbegin();
                    d = min(d, dis(N, i, k, 1));
                    d = min(d, dis(N, i, k, 2));
                    calc(d, N, i);
                }
            }
            //cout << "Current Max : " << ma << ' ' << ix <<' ' << iy << '\n';
            while(!S2.empty()) {
                auto it = *S2.begin();
                //cout << "Is right? : " << -it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
                if(A[it[1]][it[2]]) {
                    S2.erase(it);
                }
                else if(get_dis(it[1], it[2]) != -it[0]) {
                    recalc(it[1], it[2]);
                }
                else break;
            }
            if(!S2.empty()) {
                auto it = *S2.begin();
                calc(-it[0], it[1], it[2]);
                //cout << -it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
            }
            if(ma <= 1) {
                int dx = -1, dy = -1;
                for(i=1;i<=N;i++) {
                    for(int k = 1; k <= 2; k++) {
                        if(A[i][k]==0) {
                            dx = i, dy = k;
                            break;
                        }
                    }
                    if(dx!=-1) break;
                }
                calc(1, dx, dy);
            }
            if(A[ix][3-iy]==0) {
                int x = ix, y = 3 - iy;
                calc(get_dis(x, 3-y), x, 3-y);
                //cout << get_dis(x, y) << ' ' << x << ' '<< 3 - y << '\n'
            }
            if(ma >= 3 && S.size() <= 300) {
 
                int pv = -1;
                for(int n : S) {
                    if(pv==-1) {
                        pv = n;
                        continue;
                    }
                  	int sq = sqrt(ma);
                    for(int k = pv + sq; k <= n - sq; k++) {
                        if(A[k][1]==0) calc(get_dis(k, 1), k, 1);
                        if(A[k][2]==0) calc(get_dis(k, 2), k, 2);
                    }
                    pv = n;
                }
            }
            B[j] = {ix, iy};
            cout << ix << ' ' << iy << '\n';
            assert(A[ix][iy]==0);
            A[ix][iy] = 1;
            if(S.find(ix)==S.end()) {
                auto it = S.lower_bound(ix);
                if(it != S.begin()) {
                    auto it2 = it;
                    it2--;
                    int low = *it2, high = *it;
                    int d = (low + high) / 2;
                    del(d, 1);
                    del(d, 2);
                    if(low%2!=high%2) {
                        del(d+1, 1);
                        del(d+1, 2);
                    }
                }
            }
            S.insert(ix);
            auto it = S.lower_bound(ix);
            if(it != S.begin()) {
                auto it2 = it;
                it2--;
                int low = *it2;
                int d1 = (low + ix) / 2;
                recalc(d1, 1), recalc(d1, 2);
                if(low%2!=ix%2) {
                    recalc(d1+1, 1), recalc(d1+1, 2);
                }
            }
            it++;
            if(it!=S.end()) {
                int d1 = (ix + *it) / 2;
                recalc(d1, 1), recalc(d1, 2);
                if(ix%2!=*it%2) {
                    recalc(d1+1, 1), recalc(d1+1, 2);
                }
            }
        }
        if(s1=="L") {
            int k;
            cin >> k;
            k--;
            A[B[k][0]][B[k][1]] = 0;
            //cout << "Erase : " << B[k][0] << ' ' << B[k][1] << '\n';
            ix = B[k][0];
            auto it = S.lower_bound(ix);
            vector<array<int , 2>> VC;
            if(it != S.begin()) {
                auto it2 = it;
                it2--;
                int low = *it2;
                int d1 = (low + ix) / 2;
                VC.push_back({d1, 1});
                VC.push_back({d1, 2});
                if(low%2!=ix%2) {
                    VC.push_back({d1+1, 1});
                    VC.push_back({d1+1, 2});
                }
            }
            it++;
            if(it!=S.end()) {
                int d1 = (ix + *it) / 2;
                VC.push_back({d1, 1});
                VC.push_back({d1, 2});
                if(ix%2!=*it%2) {
                    VC.push_back({d1+1, 1});
                    VC.push_back({d1+1, 2});
                }
            }
            if(A[B[k][0]][3-B[k][1]]==0) {
                S.erase(B[k][0]);
                for(auto it : VC) del(it[0], it[1]);
                if(S.size() >= 2) {
                    auto it = S.lower_bound(ix);
                    if(it!=S.begin() && it != S.end()) {
                        auto it2 = it;
                        it2--;
                        int low = *it2, high = *it;
                        int d = (low +high) / 2;
                        recalc(d, 1), recalc(d, 2);
                        if(low%2!=high%2) {
                            recalc(d+1, 1), recalc(d+1, 2);
                        }
                    }
                }
            }
            else {
                for(auto it : VC) recalc(it[0], it[1]);
            }
        }
    }
}

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