글 읽기 - c++, c++17 의 차이?, 기타

atomzeno 4년 전 2

c++17로 돌려서 맞긴 했는데

c++로 저 코드를 제출하면 시간 초과가 뜨더라고요

stack 영역 할당 에서 두 버젼이 뭔가 서로 다른 부분이 있는 건가요?

#include<stdio.h>
#include<vector>
using namespace std;
typedef long long int ll;
const int MX = 1<<19;
const int N = 100001;
const int SZN = 200002;
vector<int> edge[N];
typedef struct Segtree {
	int start, i;
	ll val[MX], pl[MX];
	Segtree() {
		start = MX / 2;
		for (i = 0; i < MX; i++) {
			val[i] = pl[i] = (ll)0;
		}
	}
	void update(int n, int s, int e) {
		real_upd(1, 1, start, s, e, (ll)n);
	}
	void real_upd(int node, int s, int e, int rs, int re, ll vl) {
		if (re < s || e < rs) {
			return;
		}
		if (rs <= s && e <= re) {
			pl[node] += vl;
			return;
		}
		int mid = (s + e) / 2;
		real_upd(node * 2, s, mid, rs, re, vl);
		real_upd(node * 2 + 1, mid + 1, e, rs, re, vl);
	}
	ll ans(int s) {
		return real_ans(1, 1, start, s, s);
	}
	ll real_ans(int node, int s, int e, int rs, int re) {
		int l, r, mid;
		l = node * 2, r = node * 2 + 1;
		mid = (s + e) / 2;
		val[node] += pl[node];
		if (s != e) {
			pl[l] += pl[node];
			pl[r] += pl[node];
		}
		pl[node] = (ll)0;
		if (re < s || e < rs) {
			return (ll)0;
		}
		if (rs <= s && e <= re) {
			return val[node];
		}
		return real_ans(l, s, mid, rs, re) + real_ans(r, mid + 1, e, rs, re);
	}
}SegTree;
typedef struct range {
	int s[N], e[N], cnt;
	range() {
		for (int i = 0; i < N; i++) {
			s[i] = e[i] = -1;
		}
		cnt = 0;
	}
	void dfs() {
		dfs(1, -1);
	}
	void dfs(int node, int par) {
		s[node] = ++cnt;
		for (int i : edge[node]) {
			if (i == par) {
				continue;
			}
			dfs(i, node);
		}
		e[node] = ++cnt;
	}
}range;

int main() {
	int n, m, i;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		if (x == (-1)) {
			continue;
		}
		edge[x].push_back(i);
	}

	SegTree dt2;
	range dt1;
	dt1.dfs();
	for (i = 1; i <= m; i++) {
		int type, j, w;
		scanf("%d%d", &type, &j);
		if (type == 1) {
			scanf("%d", &w);
			dt2.update(w, dt1.s[j], dt1.e[j]);
		}
		else {
			printf("%lld\n", dt2.ans(dt1.s[j]));
		}
	}
}

dyk777 4년 전 1

저도 바로 그제 다른 문제에서 동일한 이슈가 발생하여 백준슬랙에 질문하였고, 토의결과 다음과 같았습니다.

68번줄의 range based for가 c++(11 이전 번전)에선 표준이 아니었습니다. 즉, 컴파일러마다 확장 구현을 해줬는데, gcc의 확장 구현에 문제가 있다고 합니다.

atomzeno 4년 전 0

아하

이해되었습니다

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

문제

문제

출처

ICPC

c++, c++17 의 차이?, 기타

atomzeno 4년 전 2

dyk777 4년 전 1

atomzeno 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말