QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380616#8567. Cheap Constructionucup-team1766#Compile Error//Python32.8kb2024-04-07 06:47:002024-04-07 06:47:01

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 06:47:01]
  • 评测
  • [2024-04-07 06:47:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;
struct Node {
	Node *l = 0, *r = 0;
	int lo, hi, mset = inf, madd = 0, val = -inf;
	Node(int loo, int hii): lo(loo),hi(hii){}
	Node (vector<int>& v, int loo, int hii):lo(loo), hi(hii) {
		if (lo+1 < hi) {
			int mid = lo+(hi-lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = max(l->val, r->val);
		}
		else val = v[lo];
	}
	int query(int L, int R) {
		if (R <= lo || hi <= L) return -inf;
		if (L <= lo and hi <= R) return val;
		push();
		return max(l->query(L,R),r->query(L,R));
	}
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo and hi <= R) mset = val = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L,R,x);
			val = max(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo and hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val += x;
		}
		else {
			push(), l->add(L,R,x), r->add(L,R,x);
			val = max(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid ,hi);
		}
		if (mset != inf)
			l->set(lo,hi,mset), r->set(lo,hi,mset),mset=inf;
		else if (madd)
			l->add(lo,hi,madd),r->add(lo,hi,madd), madd=0;
	}
};

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& V) : jmp(1,V) {
		for (int pw=1, k=1; pw*2 <= V.size(); pw *= 2, ++k) {
			jmp.emplace_back(V.size()-pw*2+1);
			for (int j = 0; j < jmp[k].size(); j++)
				jmp[k][j] = min(jmp[k-1][j],jmp[k-1][j+pw]);
		}
	}
	T query(int a, int b) {
		assert(a<b);
		int dep = 31-__builtin_clz(b-a);
		return min(jmp[dep][a],jmp[dep][b-(1<<dep)]);
	}
};

void build(int l, int r, vector<pair<int,int>>& seq, RMQ<pair<int,int>> rmq, bool left) {
	if (l == r) return;
	if (!left) {
		int i = rmq.query(l,r).second;
		cout << "1 " << seq[i].first << '\n';
		build(0,i,seq,rmq,false);
		build(i+1,r,seq,rmq,true);
		return;
	}
	for (int i = l; i < r; i++) {
		cout << i+1 << ' ' << seq[i].first << '\n';
	}
}

void run() {
	int n; cin >> n;
	vector<pair<int,int>> seq(n); for (auto &[p,h] : seq) cin >> p >> h, p--;
	
	vector<int> _(n); iota(_.begin(),_.end(),0);
	Node *tr = new Node(_, 0, n);

	auto find = [&](int p) {
		int l = 0, r = n;
		while (l+1 < r) {
			int m = (l+r)/2;
again:
			int x = tr->query(m,m+1);
			if (x == p) {
				if (r == m+1) {
					m--;
					goto again;
				}
				r = m+1;
			} else if (x > p) r = m;
			else l = m+1;
		}
		return l;
	};

	reverse(seq.begin(),seq.end());
	vector<pair<int,int>> act(n);
	for (auto &[p,h] : seq) {
		int x = find(p);
		act[x].first = h;
		tr->add(x,n,-1);
	}
	for (int i = 0; i< n; i++) {
		act[i].second = i;
	}
	RMQ rmq(act);

	build(0, n, act,rmq,false);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t; while (t--) run();
}

詳細信息

  File "answer.code", line 2
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax