oj.uz

답안 #29284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29284 2017-07-19T01:20:15 Z 김현수(#1165) Meteors (POI11_met) C++14
74 / 100
 2836 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 300005;

ll n, m, k, a[N], req[N], s[N], e[N];
vector<ll> ter[N], swp[N];

struct met {
	ll s, e, x;
} b[N];

struct segtree {
	ll v[4*N], lim;
	void init () {
		for(lim=1;lim<=m;lim<<=1);
		for(ll i=2*lim;--i;) v[i] = 0;
	}
	void upd (ll S, ll E, ll X) {
		S += lim; E += lim;
		while(S <= E) {
			if(S%2 == 1) v[S++] += X;
			if(E%2 == 0) v[E--] += X;
			S /= 2; E /= 2;
		}
	}
	ll get (ll P) {
		ll ret = 0; P += lim;
		while(P) {ret += v[P]; P /= 2;}
		return ret;
	}
} seg;

bool can (ll I) {
	ll R = 0;
	for(auto &T : ter[I]) R += seg.get(T);
	return R >= req[I];
}

bool solve () {
	for(ll i=1;i<=n;i++) {
		if(s[i] == e[i]) continue;
		ll M = (s[i]+e[i])/2;
		swp[M].push_back(i);
	}
	seg.init();
	for(ll i=1;i<=k;i++) {
		if(b[i].s > b[i].e) {
			seg.upd(b[i].s, m, b[i].x);
			seg.upd(1, b[i].e, b[i].x);
		}
		else seg.upd(b[i].s,b[i].e,b[i].x);
		for(auto &T : swp[i]) {
			can(T) ? e[T] = i : s[T] = i+1;
		}
		swp[i].clear();
	}
	for(ll i=1;i<=n;i++) {
		if(s[i] != e[i]) return true;
	}
	return false;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++) {
		scanf("%lld",&a[i]);
		ter[a[i]].push_back(i);
	}
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&req[i]);
	}
	scanf("%lld",&k);
	for(ll i=1;i<=k;i++) {
		scanf("%lld%lld%lld",&b[i].s,&b[i].e,&b[i].x);
	}
	for(ll i=1;i<=n;i++) {
		s[i] = 1; e[i] = k+1;
	}
	while(solve());
	for(ll i=1;i<=n;i++) {
		if(s[i] == k+1) puts("NIE");
		else printf("%lld\n",s[i]);
	}
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:66:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
met.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^
met.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&req[i]);
                        ^
met.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&k);
                  ^
met.cpp:76:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&b[i].s,&b[i].e,&b[i].x);
                                                ^

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 41868 KB Output is correct
2 Correct 0 ms 42000 KB Output is correct
3 Correct 3 ms 41868 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 42000 KB Output is correct
2 Correct 0 ms 42000 KB Output is correct
3 Correct 6 ms 42000 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 43460 KB Output is correct
2 Correct 269 ms 46956 KB Output is correct
3 Correct 276 ms 45284 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 44648 KB Output is correct
2 Correct 269 ms 44676 KB Output is correct
3 Correct 279 ms 47124 KB Output is correct
4 Correct 39 ms 44732 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 43744 KB Output is correct
2 Correct 193 ms 46752 KB Output is correct
3 Correct 136 ms 42000 KB Output is correct
4 Correct 256 ms 45892 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 42548 KB Output is correct
2 Correct 256 ms 44684 KB Output is correct
3 Correct 199 ms 42924 KB Output is correct
4 Correct 316 ms 47908 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 2359 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2836 ms 65348 KB Output is correct
2 Incorrect 976 ms 46052 KB Output isn't correct
3 Halted 0 ms 0 KB -