Submission #430781

#	Time	Username	Problem	Language	Result	Execution time	Memory
430781		deadeye	Pilot (NOI19_pilot)	C++14	18 / 100	52 ms	10552 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
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> par, grpsize;
	int groups;
    DSU(int n) {
    	par.resize(n + 1), grpsize.resize(n + 1);
    	groups = n;
        for (int i = 0; i <= n; ++i) {
            par[i] = i;
            grpsize[i] = 1;
        }
    }
    int find(int x) { return (par[x]==x)? x:find(par[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        groups -= (!same(x, y));
        if (grpsize[x] < grpsize[y]) swap(x, y);
        par[y] = x;
        grpsize[x] += grpsize[y];
    }
    int getsz(int x) {return grpsize[find(x)];}
};
 
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, Q; cin >> N >> Q;
	vector<pi> H(N), Y(Q);
	for (int i = 0; i < N; ++i) {
		cin >> H[i].fi;
		H[i].si = i;
	}
	for (int i = 0; i < Q; ++i) {
		cin >> Y[i].fi;
		Y[i].si = i;
	}
	sort(H.begin(), H.end());
	sort(Y.begin(), Y.end());
	vector<int> can(N), ans(N);
	int idx = 0, sum = 0;
	DSU dsu(N);
	for (int i = 0; i < Q; ++i) {
		int ret = 0;
		while (idx < N && H[idx].fi <= Y[i].fi) {
			int pos = H[idx].si, lx = 0, rx = 0;
			can[pos] = 1;
			if (pos > 0) {
				if (can[pos - 1]) {\
					lx = dsu.getsz(pos - 1);
					dsu.unite(pos - 1, pos);
				}
			}
			if (pos < N - 1) {
				if (can[pos + 1]) {
					rx = dsu.getsz(pos + 1);
					dsu.unite(pos + 1, pos);
				}
			}
			ret += lx + rx + 1 + lx * rx;
			++idx;
		}
		ans[Y[i].si] = ret + sum;
		sum += ret;
	}
	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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