Submission #681015

#	Time	Username	Problem	Language	Result	Execution time	Memory
681015		Cross_Ratio	Tram (CEOI13_tram)	C++14	0 / 100	230 ms	23672 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;
map<int, set<array<int, 2>> > M;
int dis(int a, int b, int c, int d) {
    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;
void recalc(int a, int b) {
    S2.erase({-dist[a][b], a, 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>a) {
            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));
            }
        }
    }
    dist[a][b] = d;
    S2.insert({-d, 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;
            }
            //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();
                if(A[it[1]][it[2]]) {
                    S2.erase(it);
                }
                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);
            }
            B[j] = {ix, iy};
            cout << ix << ' ' << iy << '\n';
            A[ix][iy] = 1;
            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 high = *it;
                    int d1 = (low + high) / 2;
                    recalc(d1, 1), recalc(d1, 2);
                    if(low%2!=high%2) {
                        recalc(d1+1, 1), recalc(d1+1, 2);
                    }
                }
                it--;
            }
            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);
            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 high = *it;
                    int d1 = (low + high) / 2;
                    recalc(d1, 1), recalc(d1, 2);
                    if(low%2!=high%2) {
                        recalc(d1+1, 1), recalc(d1+1, 2);
                    }
                }
                it--;
            }
            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(A[B[k][0]][3-B[k][1]]==0) S.erase(B[k][0]);
        }
    }
}

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