Submission #379056

#	Time	Username	Problem	Language	Result	Execution time	Memory
379056		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;
        }
    }
//        cout << idx << "\n";
    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