제출 #1152178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152178		sano	마상시합 토너먼트 (IOI12_tournament)	C++20	0 / 100	0 ms	320 KiB

tournament

//#include "crocodile.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

class intervalac {
	int n;
	vec<int> l, r, in, je, m, lp, poz;
public:
	void postav(vec<int> a) {
		int vel = a.size();
		n = 1;
		while (n < vel) n *= 2;
		l.resize(2*n);
		r.resize(2*n);
		in.resize(2 * n);
		lp.resize(2 * n, 0);
		poz.resize(2 * n, 0);
		m.resize(2 * n, 0);
		a.resize(n);
		je.resize(2 * n);
		For(i, n) {
			l[i + n] = i;
			r[i + n] = i;
			in[i + n] = 1;
			je[i + n] = a[i];
			poz[i + n] = i;
		}
		rffor(i, 1, (n - 1)) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
			poz[i] = l[i];
			in[i] = in[i * 2] + in[i * 2 + 1];
			je[i] = je[i * 2] + je[i * 2 + 1];
		}
	}
	void vynuluj_u(int a, int b, int s = 1) {
		if (a > r[s] || b < l[s]) return;
		if (a <= l[s] && r[s] <= b) {
			in[s] = 0;
			return;
		}
		vynuluj_u(a, b, s * 2);
		vynuluj_u(a, b, s * 2 + 1);
		in[s] = in[s * 2] + in[s * 2 + 1];
		return;
	}
	void vynuluj_m(int a, int b, int s = 1) {
		if (a > r[s] || b < l[s]) return;
		if (a <= l[s] && r[s] <= b) {
			m[s] = (-1) * NEK;
			lp[s] = 0;
			return;
		}
		vynuluj_m(a, b, s * 2);
		vynuluj_m(a, b, s * 2 + 1);
		if (m[s * 2] >= m[s * 2 + 1]) {
			m[s] = m[s * 2];
			poz[s] = poz[s * 2];
		}
		else {
			m[s] = m[s * 2 + 1];
			poz[s] = poz[s * 2 + 1];
		}
		return;
	}
	void zmen_s(int s, int k) {
		s += n;
		je[s] = k;
		s /= 2;
		while (s) {
			je[s] = je[s * 2] + je[s * 2 + 1];
			s /= 2;
		}
		return;
	}
	int najdi(int x, int s = 1) {
		if (s >= n) return s - n;
		if (in[s * 2] > x) {
			return najdi(x, s * 2);
		}
		return najdi(x - in[s * 2], s * 2 + 1);
	}
	pii maxi(int a, int b, int s = 1) {
		if (a > r[s] || b < l[s]) return { (-1) * NEK, 0 };
		if (a <= l[s] && r[s] <= b) return { m[s], poz[s] };
		if (lp[s] != 0) {
			lp[s] = 0;
			lp[s * 2] = 1;
			lp[s * 2 + 1] = 1;
			m[s * 2] = (-1) * NEK;
			m[s * 2 + 1] = (-1) * NEK;
		}
		pii m1 = maxi(a, b, s * 2); pii m2 = maxi(a, b, s * 2 + 1);
		if (m1.ff >= m2.ff) {
			return m1;
		}
		return m2;
	}


	void zmen_m(int x, pii k, int s = 1) {
		if (x > r[s] || x < l[s]) return;
		if (x <= l[s] && r[s] <= x) {
			m[s] = k.ff;
			poz[s] = k.ss;
			return;
		}
		if (lp[s] != 0) {
			lp[s] = 0;
			lp[s * 2] = 1;
			lp[s * 2 + 1] = 1;
			m[s * 2] = (-1) * NEK;
			m[s * 2 + 1] = (-1) * NEK;
		}
		zmen_m(x, k, s * 2);
		zmen_m(x, k, s * 2 + 1);
		if (m[s * 2] >= m[s * 2 + 1]) {
			m[s] = m[s * 2];
			poz[s] = poz[s * 2];
		}
		else {
			m[s] = m[s * 2 + 1];
			poz[s] = poz[s * 2 + 1];
		}
		return;
	}
	int suc(int a, int b, int s = 1) {
		if (a > r[s] || b < l[s]) return 0;
		if (a <= l[s] && r[s] <= b) return je[s];
		return (suc(a, b, s * 2) + suc(a, b, s * 2 + 1));
	}
};


int GetBestPosition(int n, int c, int r, int k[100], int s[100], int e[100]) {
	intervalac seg;
	vec<int> a(n, 0);
	For(i, (n-1)) {
		if (k[i] > r) a[i] = 1;
	}
	seg.postav(a);
	int maxi = 0;
	int maxipoz = 0;
	For(i, c) {
		int p1 = seg.najdi(s[i]), p2 = seg.najdi(e[i]);
		int suc = seg.suc(p1, p2 - 1);
		if (suc > 0) {
			seg.vynuluj_m(p1, p2);
			seg.vynuluj_u(p1 + 1, p2);
			seg.zmen_s(p1, 1);
		}
		if (suc == 0) {
			pii nm = seg.maxi(p1, p2);
			nm.ff++;
			if (nm.ff > maxi) {
				maxi = nm.ff;
				maxipoz = nm.ss;
			}
			seg.vynuluj_u(p1 + 1, p2);
			seg.zmen_m(p1, nm);
		}
	}
	return maxipoz;
}

/*
signed main() {
	int n, c, r; cin >> n >> c >> r;
	int k[100], s[100], e[100];
	For(i, (n - 1)) cin >> k[i];
	For(i, c) cin >> s[i] >> e[i];


	cout << GetBestPosition(n, c, r, k, s, e) << '\n';
	return 0;
}*/

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51