Submission #502656

#	Time	Username	Problem	Language	Result	Execution time	Memory
502656		banterbry	Pilot (NOI19_pilot)	C++17	100 / 100	481 ms	56048 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg>
void __f(string name, Arg arg) {
	cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
	string cur = "";
	for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
	string nxt = names.substr(cur.size()+2);
	cerr << cur << " = " << head << ", ";
	__f(nxt, tail...);
}

struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N, -1); }
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }  
    bool same_set(int a, int b) { return get(a) == get(b); }    
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {  // union by size
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	vector<pi> A(N), qq(Q);
	vector<ll> ans(Q), flag(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i].fi;
		A[i].si = i;
	}
	for (int i = 0; i < Q; ++i) {
		cin >> qq[i].fi;
		qq[i].si = i;
	}
	DSU dsu(N);
	sort(A.begin(), A.end());
	sort(qq.begin(), qq.end());
	ll idx = 0, sum = 0;
	for (auto i: qq) {
		ll ret = 0;
		while (idx < N && A[idx].fi <= i.fi) {
			ll pos = A[idx].si, lx = 0, rx = 0;
			if (pos > 0 && flag[pos - 1]) {
				lx = dsu.size(pos - 1);
				dsu.unite(pos, pos - 1);
			}
			if (pos < N - 1 && flag[pos + 1]) {
				rx = dsu.size(pos + 1);
				dsu.unite(pos, pos + 1);	
			}
			ret += lx + rx + lx * rx + 1;
			flag[pos] = 1;
			++idx;
		}
		ans[i.si] = ret + sum;
		sum += ret;
	}
	for (auto i: ans) cout << i << '\n';
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11