QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876665#7627. PhonychangziliangCompile Error//C++145.4kb2025-01-31 10:53:522025-01-31 10:53:52

Judging History

This is the latest submission verdict.

  • [2025-01-31 10:53:52]
  • Judged
Show
  • [2025-01-31 10:53:52]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
typedef __int128 Int;
int n, m;
LL K, a[N], Lim;
namespace Segment {
	struct SegmentTree {
		int ls, rs, cnt;
		#define ls(x) tree[x].ls
		#define rs(x) tree[x].rs
		#define cnt(x) tree[x].cnt
	}tree[N * 40];
	int tot;
	int newnode() {return ++ tot;}
	void update(int p) {
		cnt(p) = cnt(ls(p)) + cnt(rs(p));
	}
	void ins(int &p, LL lp, LL rp, LL pos) {
		if(!p) p = newnode();
		if(lp == rp) {
			cnt(p) ++;
			return ;
		}
		LL mid = (lp + rp >> 1);
		if(pos <= mid) ins(ls(p), lp, mid, pos);
		else ins(rs(p), mid + 1, rp, pos);
		update(p);
	}
	LL ask(int p, LL lp, LL rp, int x) {
		//cout << "GGG" << ' ' << lp << ' ' << rp
		if(lp == rp) return lp;
		LL mid = (lp + rp >> 1);
		if(cnt(ls(p)) >= x) return ask(ls(p), lp, mid, x);
		else return ask(rs(p), mid + 1, rp, x - cnt(ls(p)));
 	}
 	int Merge(int p, int q, LL lp, LL rp) {
 		if(!p || !q) return p ^ q;
 		if(lp == rp) {
 			cnt(p) += cnt(q);
 			return p;
		}
		LL mid = (lp + rp >> 1);
		ls(p) = Merge(ls(p), ls(q), lp, mid);
		rs(p) = Merge(rs(p), rs(q), mid + 1, rp);
		update(p);
		return p;
	}
	void split(int &p, int &q, LL lp, LL rp, LL c) {
		if(!p) return ;
		if(lp == rp) {
			if(cnt(p) == c) {
				q = p; p = 0;
				return ;
			}
			else {
				int u = newnode();
				cnt(u) = c; cnt(p) -= c;
			    q = u;
				return ;
			}
		}
		if(!q) q = newnode();
		LL mid = (lp + rp >> 1);
		if(cnt(rs(p)) >= c) split(rs(p), rs(q), mid + 1, rp, c);
		else {
			rs(q) = rs(p); rs(p) = 0;
			split(ls(p), ls(q), lp, mid, c - cnt(rs(q)));
		}
		update(p); update(q);
	}
}
namespace Fhq { // 改成平衡树   空间线性 
	int root, tot;
	int rt1, rt2, rt3;
	mt19937_64 rnd(time(0));
	struct Node {
		int son[2];
		int cnt, sz, rt; // 数量， 根 
		LL val, w; // 数值  随机权重 
	}t[N * 2];
	int newnode(LL v) {
		tot ++;
		t[tot].val = v;
		t[tot].w = rnd();
		return tot;
	}
	void ins(int p, LL v) {
		Segment::ins(t[p].rt, 0, K - 1, v);
		t[p].cnt ++; t[p].sz ++;
	}
	void update(int p) {
		t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + t[p].cnt;
	}
	int Merge(int p, int q) {
	    if(!p || !q) return p ^ q;	
	    if(t[p].w > t[q].w) {
	    	t[p].son[1] = Merge(t[p].son[1], q);
	    	update(p);
	    	return p;
		}
		else {
			t[q].son[0] = Merge(p, t[q].son[0]);
			update(q);
			return q;
		}
	}
	void split(int p, int &x, int &y, LL lim) {
		if(!p) {x = y = 0; return ;}
		if(t[p].val <= lim) x = p, split(t[p].son[1], t[p].son[1], y, lim);
		else y = p, split(t[p].son[0], x, t[p].son[0], lim);
		update(p);
	}
	void add(LL v1, LL v2) { // 插入一个 
		split(root, rt1, rt2, v1);
		split(rt1, rt1, rt3, v1 - 1);
		if(!rt3) rt3 = newnode(v1);
		ins(rt3, v2);
		root = Merge(Merge(rt1, rt3), rt2);
	}
	LL query(int p, int x) { // 查询第 x 个 
	  //  if(!p) return 0;
		if(t[t[p].son[0]].sz >= x) return query(t[p].son[0], x);
		else if(t[t[p].son[0]].sz + t[p].cnt >= x) return 1LL * t[p].val * K + Segment::ask(t[p].rt, 0, K - 1, x - t[t[p].son[0]].sz);
		else return query(t[p].son[1], x - (t[t[p].son[0]].sz + t[p].cnt));
	}
	LL Find(int p, LL x) {
		if(!p) return -2e18;
		if(t[p].son[1] && t[t[p].son[1]].val <= x) return Find(t[p].son[1], x);
		else if(t[p].val <= x) return t[p].val;
		else return Find(t[p].son[0], x);
 	}
 	LL Count(int p, LL x) {
 		if(t[p].val == x) return t[p].cnt;
 		if(t[p].val > x) return Count(t[p].son[0], x);
 		else return Count(t[p].son[1], x);
	}
	int del(LL x) { // 删去值为 x 的节点，并且返回它的根 
		split(root, rt1, rt2, x);
		split(rt1, rt1, rt3, x - 1); // 删掉 rt3 的根 
		root = Merge(rt1, rt2);
		return t[rt3].rt;
	}
	void Crt(LL x, int p) {
		split(root, rt1, rt2, x);
		split(rt1, rt1, rt3, x - 1);
		if(!rt3) rt3 = newnode(x);
		t[rt3].rt = p; 
		t[rt3].sz = t[rt3].cnt = Segment::cnt(p);
		root = Merge(Merge(rt1, rt3), rt2);
	}
	void Mg(LL x, LL y) { // 把 y 删掉， 合并到 x 里面 
		int p = del(x), q = del(y);
		p = Segment::Merge(p, q, 0, K - 1);
		Crt(x, p);
	}
	void Sp(LL x, LL c) {
		int p = del(x), q = del(x - 1);
		int Rt = 0;
		Segment::split(p, Rt, 0, K - 1, c);
		Crt(x, p); q = Segment::Merge(q, Rt, 0, K - 1);
		Crt(x - 1, q);
	}
}
void move(LL x) { // 将最大的减少K  x次    方法是每次找到最后一个1，看能不能和前面那个合并，然后在分裂一次 
	while(x) {
		LL lst = Fhq::Find(Fhq::root, 1e18); // 找到 
		LL pre = Fhq::Find(Fhq::root, lst - 1);
		LL ct = Fhq::Count(Fhq::root, lst);
		if(pre >= -1e18 && (Int)(lst - pre) * ct <= x) {
			x -= (lst - pre) * ct;
			Fhq::Mg(pre, lst);
			continue;
		}
		LL step = x / ct; // 整体移动 step 
		int rt = Fhq::del(lst);
		Fhq::Crt(lst - step, rt); // 改变根 
		x -= ct * step; // 还剩下的需要分裂 
		if(x) Fhq::Sp(lst - step, x); // 分裂
		x = 0;
	}
}
int main() {
	scanf("%d%d%lld", &n, &m, &K);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%lld", &a[i]);
		Fhq::add(a[i] / K, a[i] % K);
	}
	for(int i = 1; i <= m; i ++ ) {
		char opt; LL x;
		scanf("\n%c%lld", &opt, &x);
		if(opt == 'C') { // 修改 
			move(x); // 移动 x 步 
		} 
		else { // 查询第x大 
			if(Fhq::t[Fhq::root].sz == n) printf("%lld\n", Fhq::query(Fhq::root, n - x + 1));
			else {
				puts("CNM %d\n", Fhq::t[Fhq::root].sz);
				exit(0);
			}
		}
	}
	return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/
源文件, 语言: C++14

详细 

answer.code: In function ‘int main()’:
answer.code:199:37: error: too many arguments to function ‘int puts(const char*)’
  199 |                                 puts("CNM %d\n", Fhq::t[Fhq::root].sz);
      |                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/cstdio:42,
                 from /usr/include/c++/14/ext/string_conversions.h:45,
                 from /usr/include/c++/14/bits/basic_string.h:4154,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from answer.code:1:
/usr/include/stdio.h:724:12: note: declared here
  724 | extern int puts (const char *__s);
      |            ^~~~
answer.code:185:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  185 |         scanf("%d%d%lld", &n, &m, &K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
answer.code:187:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  187 |                 scanf("%lld", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
answer.code:192:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  192 |                 scanf("\n%c%lld", &opt, &x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
English 繁體中文 简体中文

服务器时间: 2025-02-07 02:18:16 | 开源项目