글 읽기 - 고수분들 질문 부탁드려요 ㅠㅠ

khx1712 4년 전 0

코드에서 구조체부분의 operator에서

bool operator < (const query &O){

int x = high / sz;

int y = O.high / sz;

return x == y ? low < O.low : x < y;

}

를

bool operator < (const query &O){

int x = low / sz;

int y = O.low / sz;

return x == y ? low < O.low : x < y;

}

으로 바꾸면 왜 시간초과가 날까요 구글링해보니 low로 시간초과가 나지 않은 코드들도 많던데
무슨 문제일까요 ㅠㅠ

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

int sz;
int N;
int arr[100001];
long long ans[100001];
long long cnt[1000001];

typedef struct query {
	int low, high, num;
	bool operator < (const query &O){
		int x = high / sz;
		int y = O.high / sz;
		return x == y ? low < O.low : x < y;
	}
}Query;
Query qry[100000];

int main() {
	long long res;
	int T, low, high;
	cin >> N >> T;
	sz = sqrt(N);
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	for (int i = 0; i < T; i++) {
		cin >>low >> high;
		qry[i] = { low - 1, high - 1, i };
	}
	sort(qry, qry + T);

	low = qry[0].low, high = qry[0].low-1;
	res = 0;
	for (int i = 0; i < T; i++) {
		while (qry[i].low < low) {
			low--;
			res -= cnt[arr[low]] * cnt[arr[low]] * arr[low];
			cnt[arr[low]]++;
			res += cnt[arr[low]] * cnt[arr[low]] * arr[low];
		}
		while (qry[i].low > low) {
			res -= cnt[arr[low]] * cnt[arr[low]] * arr[low];
			cnt[arr[low]]--;
			res += cnt[arr[low]] * cnt[arr[low]] * arr[low];
			low++;
		}
		while (qry[i].high < high) {
			res -= cnt[arr[high]] * cnt[arr[high]] * arr[high];
			cnt[arr[high]]--;
			res += cnt[arr[high]] * cnt[arr[high]] * arr[high];
			high--;
		}
		while (qry[i].high > high) {
			high++;
			res -= cnt[arr[high]] * cnt[arr[high]] * arr[high];
			cnt[arr[high]]++;
			res += cnt[arr[high]] * cnt[arr[high]] * arr[high];
		}
		ans[qry[i].num] = res;
	}

	for (int i = 0; i < T; i++) {
		cout << ans[i] << '\n';
	}
}

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

문제

문제

출처

ICPC

고수분들 질문 부탁드려요 ㅠㅠ

khx1712 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말