Submission #379033

#	Time	Username	Problem	Language	Result	Execution time	Memory
379033		gustason	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	364 KiB

xylophone

    #include "xylophone.h"
    #include<bits/stdc++.h>
    using namespace std;

    map<pair<int, int>, int> m;
    int qq(int L, int R) {
        if (m[{L, R}] != 0) {
            return m[{L, R}];
        }
        return m[{L, R}] = query(L, R);
    }
    void solve(int n) {
        int l = 1, r = n, idx = r;
        while(l <= r) {
            int mid = (l + r) / 2;
            if (qq(mid, n) == n-1) {
                idx = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        vector<bool> seen(n+5, false);
        vector<int> an(n+5, -1);
        an[idx] = 1;
        if (idx != 1) {
            int val = qq(idx-1, idx);
            an[idx-1] = val - 1;
            seen[val] = true;
        }
        for(int i = idx-2; i >= 1; i--) {
            int val = qq(i, idx);
            if (!seen[val]) {
                an[i] = val - 1;
                seen[val] = true;
            } else {
                an[i] = an[i+1] - qq(i, i+1);
            }
        }

        if (idx != n) {
            int val = qq(idx, idx+1);
            an[idx+1] = val - 1;
            seen[val] = true;
        }
        for(int i = idx+2; i <= n; i++) {
            int val = qq(idx, i);
            if (!seen[val]) {
                an[i] = val - 1;
                seen[val] = true;
            } else {
                an[i] = an[i-1] - qq(i-1, i);
            }
        }
        for(int i = 1; i <= n; i++) {
            answer(i, an[i]);
        }

    }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53