Submission #240647

#	Time	Username	Problem	Language	Result	Execution time	Memory
240647		osaaateiasavtnl	Abduction 2 (JOI17_abduction2)	C++14	0 / 100	8 ms	768 KiB

abduction2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 50007;
int a[2][N];
int l[2][N], r[2][N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[0][i];
    }   
    for (int i = 0; i < m; ++i) {
        cin >> a[1][i];
    }   
    
    struct Line {
        int t;
        int i, x;
    };

    auto comp = [&](Line a, Line b) {
        return a.x > b.x;
    };     

    vector <Line> s;                      
    for (int i = 0; i < n; ++i) {
        s.app({0, i, a[0][i]});
    }   
    for (int i = 0; i < m; ++i) {
        s.app({1, i, a[1][i]});
    }   
    sort(all(s), comp);

    while (q--) {
        int x, y;
        cin >> x >> y;
        --x; --y;

        vector <int> bor[2];
        bor[0] = {-1, m};
        bor[1] = {-1, n};
        for (int t = 0; t < 2; ++t) {
            for (int i = 0; i < bor[t].back(); ++i) {
                l[t][i] = i - bor[t][0];
                r[t][i] = bor[t].back() - i;
            }
        }

        //slx - start go left on horizontal line

        int slx = -1;
        for (int i = y - 1; i >= 0; --i) {
            if (a[1][i] > a[0][x]) {
                slx = i;
                break;
            }   
        }   
        int srx = m;
        for (int i = y + 1; i < m; ++i) {
            if (a[1][i] > a[0][x]) {
                srx = i;
                break;
            }   
        }   

        int sly = -1;
        for (int i = x - 1; i >= 0; --i) {
            if (a[0][i] > a[1][y]) {
                sly = i;
                break;
            }   
        }   
        int sry = n;
        for (int i = x + 1; i < n; ++i) {
            if (a[0][i] > a[1][y]) {
                sry = i;
                break;
            }   
        }   

        int ans = 0;

        ans = max(ans, y - slx);
        ans = max(ans, srx - y);
        ans = max(ans, x - sly);
        ans = max(ans, sry - x);

        for (auto e : s) {
            
            if (e.t == 0) {
                cout << "row " << e.i << endl;
                for (int i = 0; i < m; ++i) 
                    cout << l[0][i] << ' ';
                cout << endl;
                for (int i = 0; i < m; ++i) 
                    cout << r[0][i] << ' ';
                cout << endl;
                cout << endl;
            }   
            else {
                cout << "col " << e.i << endl;
                for (int i = 0; i < n; ++i) 
                    cout << l[1][i] << ' ';
                cout << endl;
                for (int i = 0; i < n; ++i) 
                    cout << r[1][i] << ' ';
                cout << endl;
                cout << endl;
            }

            if (e.t == 0) {
                if (e.i == sly) {
                    ans = max(ans, max(l[e.t][y], r[e.t][y]) + x - sly);
                }   
                if (e.i == sry) {
                    ans = max(ans, max(l[e.t][y], r[e.t][y]) + sry - x);
                }   
            }
            else {
                if (e.i == slx) {
                    ans = max(ans, max(l[e.t][x], r[e.t][x]) + y - slx);
                }   
                if (e.i == srx) {
                    ans = max(ans, max(l[e.t][x], r[e.t][x]) + srx - y);
                }   
            }   

            bor[e.t^1].app(e.i);
            sort(all(bor[e.t^1]));

            int pos = -1;
            for (int i = 0; i < bor[e.t^1].size(); ++i) {
                if (bor[e.t^1][i] == e.i) {
                    pos = i;
                    break;
                }   
            }   

            int link_l = bor[e.t^1][pos - 1];
            for (int i = link_l + 1; i <= e.i; ++i) {

                cout << "upd " << i << endl;
                if (i == 1) {
                    cout << "tak " << e.i - i << ' ' << max(l[e.t][i], r[e.t][i]) << endl;
                }   

                r[e.t^1][i] = e.i - i + max(l[e.t][i], r[e.t][i]);
            }   

            int link_r = bor[e.t^1][pos + 1];
            for (int i = e.i; i < link_r; ++i) {
                l[e.t^1][i] = i - e.i + max(l[e.t][i], r[e.t][i]);
            }   

            if (e.t == 1) {
                exit(0);
            }
        }   

        --ans;
        cout << ans << endl;
    }   
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:150:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < bor[e.t^1].size(); ++i) {
                             ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 10
• Subtask 3: 0 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56