Submission #216733

#	Time	Username	Problem	Language	Result	Execution time	Memory
216733		ainta	Treatment Project (JOI20_treatment)	C++17	100 / 100	1107 ms	106336 KiB

treatment

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define pii pair<int,int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define N_ 101000
#define SZ 131072

using namespace std;
struct AA {
	int t, l, r, c;	
}P[N_];
long long D[N_], INF = 1e18;
int L, n;
struct Tree {
	int X[N_], Y[N_], Loc[N_][20];
	int n, PV[SZ+SZ], ReNum[N_];
	pli IT[SZ + SZ], MM[SZ+SZ];
	vector<pii>TP;
	vector<int>YY[SZ + SZ], Num[SZ+SZ], chk[SZ + SZ];
	set<pil>Set[SZ + SZ];
	
	struct point {
		int y, num;
	}w[N_];
	void Add(AA t, int num) {
		n++;
		X[n] = t.l + t.t;
		Y[n] = t.l - t.t;
		TP.push_back({ X[n],n });
	}
	void Calc2(int nd) {
		while (PV[nd] < chk[nd].size() && chk[nd][PV[nd]])PV[nd]++;
		if (PV[nd] == chk[nd].size()) {
			MM[nd] = { INF,0 };
			return;
		}
		auto it = Set[nd].lower_bound({ PV[nd],0ll });
		if (it == Set[nd].end()) {
			MM[nd] = { INF,0 };
			return;
		}
		MM[nd] = { it->second, Num[nd][PV[nd]] };
	}
	void UDT(int nd, int b, int e) {
		IT[nd] = MM[nd];
		if (b == e)return;
		IT[nd] = min(IT[nd], min(IT[nd * 2], IT[nd * 2 + 1]));
	}
	void Build(int nd, int b, int e, int dep) {
		int i;
		vector<pii>V;
		for (i = b; i <= e; i++) V.push_back({ w[i].y,w[i].num });
		sort(V.begin(), V.end());
		int sz = V.size();
		YY[nd].resize(sz);
		chk[nd].resize(sz);
		Num[nd].resize(sz);
		PV[nd] = 0;
		for (i = 0; i < sz; i++)chk[nd][i] = 0;
		for (i = 0; i < sz; i++) {
			YY[nd][i] = V[i].first;
			Num[nd][i] = V[i].second;
			Loc[V[i].second][dep] = i;
		}
		MM[nd] = IT[nd] = { INF,0 };
		if (b == e)return;
		int m = (b + e) >> 1;
		Build(nd * 2, b, m, dep + 1);
		Build(nd * 2 + 1, m + 1, e, dep + 1);
		UDT(nd, b, e);
	}
	void init() {
		sort(X + 1, X + n + 1);
		sort(TP.begin(), TP.end());
		int cc = 0;
		for (auto &t : TP) {
			int x = t.second;
			w[++cc] = { Y[x],x };
			ReNum[x] = cc;
		}
		Build(1, 1, n, 0);
	}
	void Del2(int nd, int b, int e, int x, int dep) {
		if (Loc[x][dep] >= chk[nd].size()) {
			while (1) {}
		}
		chk[nd][Loc[x][dep]] = 1;
		Calc2(nd);
		if (b != e) {
			int m = (b + e) >> 1;
			if (ReNum[x] <= m)Del2(nd * 2, b, m, x, dep + 1);
			else Del2(nd * 2 + 1, m + 1, e, x, dep + 1);
		}
		UDT(nd, b, e);
	}
	void Del(int a) {
		Del2(1, 1, n, a, 0);
	}
	void Put2(int nd, int y, long long g) {
		int pv = lower_bound(YY[nd].begin(), YY[nd].end(), y + 1) - YY[nd].begin();
		if (!pv)return;
		pv--;
		auto it = Set[nd].lower_bound({ pv,-1ll });
		if (it != Set[nd].end() && it->second <= g)return;
		if (it != Set[nd].end() && it->first == pv)Set[nd].erase(it);
		Set[nd].insert({ pv,g });
		it = Set[nd].find({ pv,g });
		while (it!=Set[nd].begin()) {
			auto it2 = it; it2--;
			if (it2->second >= g)Set[nd].erase(it2);
			else break;
		}
	}
	void Put(int nd, int b, int e, int s, int l, int y, long long g, int dep) {
		if (s > l)return;
		if (s <= b && e <= l) {
			Put2(nd, y, g);
			Calc2(nd);
			UDT(nd, b, e);
			return;
		}
		int m = (b + e) >> 1;
		if (s <= m)Put(nd * 2, b, m, s, l, y, g, dep + 1);
		if (l > m)Put(nd * 2 + 1, m + 1, e, s, l, y, g, dep + 1);
		UDT(nd, b, e);
	}
	void Ins(int x, int y, long long g) {
		int pv = lower_bound(X + 1, X + n + 1, x + 1) - X;
		pv--;
		Put(1, 1, n, 1, pv, y, g, 0);
	}
}T;
void Insert(int a) {
	T.Ins(P[a].r+1 + P[a].t, P[a].r+1 - P[a].t, D[a]);
	T.Del(a);
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i, j;
	scanf("%d%d", &L, &n);
	T.n = 0;
	for (i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &P[i].t, &P[i].l, &P[i].r, &P[i].c);
		T.Add(P[i], i);
		D[i] = INF;
	}
	T.init();
	for (i = 1; i <= n; i++) {
		if (P[i].l == 1) {
			D[i] = P[i].c;
			Insert(i);
		}
	}
	while (1) {
		pli tp = T.IT[1];
		if (tp.first > 1e17)break;
		D[tp.second] = tp.first + P[tp.second].c;
		Insert(tp.second);
	}
	long long res = INF;
	for (i = 1; i <= n; i++) {
		if (P[i].r == L)res = min(res, D[i]);
	}
	if (res > 1e17)res = -1;
	printf("%lld\n", res);
}

Compilation message (stderr)

treatment.cpp: In member function 'void Tree::Calc2(int)':
treatment.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (PV[nd] < chk[nd].size() && chk[nd][PV[nd]])PV[nd]++;
          ~~~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:36:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (PV[nd] == chk[nd].size()) {
       ~~~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp: In member function 'void Tree::Del2(int, int, int, int, int)':
treatment.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (Loc[x][dep] >= chk[nd].size()) {
       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:142:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
treatment.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &L, &n);
  ~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &P[i].t, &P[i].l, &P[i].r, &P[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61