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

这个题线段树能过!47ms,之前打错了一个参数搞死循环了TLE。。。

Posted by KatrineYang at 2016-09-18 12:09:14 on Problem 1341
#include <iostream>
#include <stdio.h>
using namespace std;

int N, M;
int a1, a2, a3, s1, s2, s3, e1, e2, e3;

int xds[200002];

int mum[50005];

int S(long long int i){
	long long int ans = i*i*s1 + i*s2 + s3;
	return (int)(ans%(N/2));
}

int E(long long int i, int s){
	long long int ans = i*i*e1 + i*e2 + e3;
	return s + (int)(ans%(N/2));
}

int A(long long int i){
	long long int ans = i*i*a1 + i*a2 + a3;
	return (int)(ans%9973);
}

int mn(int a, int b){
	return (a<b) ? a : b;
}

void jxds(int start, int end, int bh){
	if(start == end){
		xds[bh] = A(start);
		return;
	}
	int mid = (start+end)/2;
	jxds(start, mid, 2*bh+1);
	jxds(mid+1, end, 2*bh+2);
	xds[bh] = mn(xds[2*bh+1], xds[2*bh+2]);
}

int cx(int cxStart, int cxEnd, int xzStart, int xzEnd, int bh){
	if(cxStart == xzStart && cxEnd == xzEnd){
		return xds[bh];
	}
	int xzMid = (xzStart+xzEnd)/2;
	if(cxEnd <= xzMid){
		return cx(cxStart, cxEnd, xzStart, xzMid, 2*bh+1);
	}
	else if(cxStart > xzMid){
		return cx(cxStart, cxEnd, xzMid+1, xzEnd, 2*bh+2);
	}
	else{
		int hx1 = cx(cxStart, xzMid, xzStart, xzMid, 2*bh+1);
		int hx2 = cx(xzMid+1, cxEnd, xzMid+1, xzEnd, 2*bh+2);
		return mn(hx1, hx2);
	}
}

int cx(int s, int e){
	return cx(s, e, 0, N-1, 0);
}

int main() {
	int t;
	scanf("%d", &t);
	for(int ii = 0; ii < t; ii++){
		scanf("%d%d%d%d%d%d%d%d%d%d%d", &N , &a1, &a2, &a3, &M ,&s1, &s2, &s3, &e1, &e2, &e3);
		jxds(0, N-1, 0);
		int mx = 0;
		for(int i = 0; i < M; i++){
			int si = S(i);
			int ei = E(i, si);
			mum[i] = cx(si, ei);
			//cout << mum[i] << endl;
			if(mum[i] > mx) mx = mum[i];
		}
		for(int i = 0; i < M; i++){
			if(mum[i] == mx){
				printf("%d\n", i);
				break;
			}
		}
	}
	return 0;
}

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