글 읽기 - 시간 초과가 나는데 어떻게 해결해줘야 될지 막막하네요

dfwdf77 6년 전 0

일단 원의 왼쪽점을 기준으로 벡터에 넣고

N개의 따라 벡터로 기준으로 세그먼트 트리를 만들어서 돌렸는데

시간 초과가 나네요

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 300000
int seg[4*MAX];
typedef struct node{
	int left;
	int right;
}NN;

NN arr[300001];
vector<int > V;
int N;

int update(int lo,int hi, int val, int node, int x, int y) {
    if ( y<lo  || hi < x)
        return seg[node];
    if (x == y)
        return seg[node] += val;
    int mid = (x + y) >> 1;
    return seg[node] = update(lo,hi, val, node * 2, x, mid) + update(lo, hi,val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return seg[node]=query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}

int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		arr[i].left=a-b;
		arr[i].right=a+b;
		V.push_back(a-b);
	}
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
//	for(int i=0;i<V.size();i++)
	//	printf("%d ",V[i]);
	//printf("\n");
	for(int i=1;i<=N;i++)
	{
		int L=0;
		int R=0;
		for(int k=0;k<V.size();k++)
		{
			if(arr[i].left>=V[k])
				L=k+1;
			if(arr[i].right>=V[k])
				R=k+1;
		}
	
		//printf("%d %d %d\n",i,L,R);
		update(L,R,1,1,1,V.size());
	}
	printf("%d\n",seg[1]);
	int ss;
	scanf("%d",&ss);
}

sgchoi5 6년 전 0

COCI 문제는 TC 가 공개되어 있으니 처리를 많이 해야 하는 상황에서 잘 동작하는지 보시면 될 것 같고..

http://gooddaytocode.blogspot....

영문으로 된 문제 설명이 도움이 되실 수 있으면, 보셔도 되고요... judge solution 코드를 분석해보셔서 어떻게 처리하고 있는지 보셔도 될 것 같고요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과가 나는데 어떻게 해결해줘야 될지 막막하네요

dfwdf77 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말