제출 #500699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500699		pooty	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	330 ms	29088 KiB

triusis

#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
class SegmentTree {
public:
	vi prop;
	vi val;
	int n;
	SegmentTree(int n) {
		this-> n = n;
		val.assign(4*n, INF);
		prop.assign(4*n,0);
	}
	int l(int p) {
		return p*2;
	}
	int r(int p) {
		return p*2+1;
	}
	void propagate(int p, int L, int R) {
		if (prop[p] != 0) {
			val[p] += prop[p];
			if (L!=R) {
				int m = (L+R)/2;
				prop[l(p)] += prop[p];
				prop[r(p)] += prop[p];
			} 
			prop[p]= 0;
		} 
	}
	int RMQ(int p, int L , int R, int i, int j) {
		propagate(p, L, R);
		if (R< i || L > j ) return INF;
		if (L >= i && R <= j) return val[p];
		int m = (L+R)/2;
		return min(RMQ(l(p), L, m, i, j), RMQ(r(p), m+1, R, i, j));
	}
	void pointupdate(int p, int L, int R, int x, int newval) {
		propagate(p, L,R);
		if (R<x|| L>x ) return;
		if (L== x && R== x) {
			val[p] = newval;
			return;
		}
		int m = (L+R)/2;
		pointupdate(l(p), L, m,x, newval);
		pointupdate(r(p), m+1, R, x, newval);
		val[p] = min(val[r(p)], val[l(p)]);
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	vi arr = {n*m};
	REP(i, n) {
		int x;cin>>x;
		x += (n-i-1)*m;
		arr.push_back(x);
	}
	set<int> allval;
	for (auto x:arr) {
		allval.insert(x);
	}
	map<int,int> comp;
	int idx =0;
	for (auto x: allval) {
		comp[x] = idx++;
	}
	vi farr;
	for (auto x: arr) {
		farr.push_back(comp[x]);
	}
	SegmentTree tr(idx);
	tr.pointupdate(1, 0, idx-1, farr[0], 0);
	REPL(i,1, n+1) {
		int bstval = tr.RMQ(1,0,idx-1,farr[i], idx-1);
		tr.prop[1]++;
		tr.pointupdate(1,0,idx-1,farr[i], bstval);
	}
	cout<<tr.RMQ(1,0,idx-1,0,idx-1);
}

컴파일 시 표준 에러 (stderr) 메시지

triusis.cpp: In member function 'void SegmentTree::propagate(int, int, int)':
triusis.cpp:41:9: warning: unused variable 'm' [-Wunused-variable]
   41 |     int m = (L+R)/2;
      |         ^

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37