Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

还是过不去求助!!

Posted by LilyLing at 2015-08-18 22:52:19 on Problem 3667
#include <cstdio>

using namespace std;

// SegTree: Structures
struct node {
	int a, b;
	node *l, *r;
	int maxs, maxl, maxr;
	int f1, f2;
};

int max3(int a, int b, int c) {
	int ret = -2147483647;
	if(a > ret) ret = a;
	if(b > ret) ret = b;
	if(c > ret) ret = c;
	return ret;
}

void update(node *p) {
	// 1.
	p->maxs = max3(p->l->maxr + p->r->maxl, p->l->maxs, p->r->maxs);
	// 2.
	p->maxl = p->l->maxl;
	if(p->l->maxl == p->l->b - p->l->a + 1) p->maxl += p->r->maxl;
	// 3.
	p->maxr = p->r->maxr;
	if(p->r->maxr == p->r->b - p->r->a + 1) p->maxr += p->l->maxr;
}

void buildtree(node *&p, int a, int b) {

	p = new node;

	p->a = a; p->b = b;
	p->l = p->r = NULL;

	p->maxs = p->maxl = p->maxr = b - a + 1;

	p->f1 = 0; p->f2 = 0;

	if(a < b) {
		int mid = (a + b) >> 1;

		buildtree(p->l, a, mid);
		buildtree(p->r, mid+1, b);
	}

}

int lookup(node *p, int x) {

	if(p->maxl >= x) return p->a;

	if(p->l->maxs >= x) return lookup(p->l, x);

	if(p->l->maxr + p->r->maxl >= x) return p->l->b - p->l->maxr + 1;

	return lookup(p->r, x);
}

void pushdown2(node *p) {
	if(p->f2 == 1) {
		p->l->maxs = p->l->maxl = p->l->maxr = p->l->b - p->l->a + 1;
		p->r->maxs = p->r->maxl = p->r->maxr = p->r->b - p->r->a + 1;
		p->l->f2 = p->r->f2 = 1;
		p->f2 = 0;
	}
}

void pushdown1(node *p) {
	if(p->f1 == 1) {
		p->l->maxs = p->l->maxl = p->l->maxr = 0;
		p->r->maxs = p->r->maxl = p->r->maxr = 0;
		p->l->f1 = p->r->f1 = 1;
		p->f1 = 0;
	}
}

void unoccupy(node *p, int a, int b) {
	// 1.
	if(a <= p->a && p->b <= b) {
		p->f2 = 1;
		p->maxl = p->maxr = p->maxs = p->b - p->a + 1;
		return ;
	}
	// 2.
	pushdown1(p);
	// 3.
	int mid = (p->a + p->b) >> 1;
	if(a <= mid) unoccupy(p->l, a, b);
	if(mid < b) unoccupy(p->r, a, b);
	// 4.
	update(p);
}

void occupy(node *p, int a, int b) {
	// 1. 
	if(a <= p->a && p->b <= b) {
		p->f1 = 1;
		p->maxl = p->maxr = p->maxs = 0;
		return ;
	}
	// 2. 
	pushdown2(p);
	// 3.
	int mid = (p->a + p->b) >> 1;
	if(a <= mid) occupy(p->l, a, b);
	if(mid < b) occupy(p->r, a, b);
	// 4. 
	update(p);
}

node * root;

int main() {
	//freopen("poj3667.in", "r", stdin);
	//freopen("poj3667.out", "w", stdout);

	int m, n;

	scanf("%d%d",&n,&m);

	buildtree(root, 1, n);

	int x, y, z;

	for(int i=1; i<=m; i++) {
		scanf("%d", &x);
		if(x == 1) {
			scanf("%d", &y);
			if(root->maxs < y)
				printf("0\n");
			else {
				z = lookup(root, y);
				printf("%d\n", z);
				occupy(root, z, y+z-1);
			}
		} else {
			scanf("%d%d", &y, &z);
			unoccupy(root, y, y+z-1);
		}
	}

}


测试数据和论坛里面的数据都过了,依然是Wrong Answer,求助!!!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator