oj.uz

Submission #29288

# Submission time Handle Problem Language Result Execution time Memory
29288 2017-07-19T01:26:03 Z khsoo01 Meteors (POI11_met) C++11
100 / 100
 3906 ms 44344 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 300005;

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

struct met {int 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);
		if(R >= req[I]) return true;
	}
	return false;
}

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();
		swp[i].shrink_to_fit();
	}
	for(ll i=1;i<=n;i++) {
		if(s[i] != e[i]) return true;
	}
	return false;
}

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

Compilation message

met.cpp: In function 'int main()':
met.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
met.cpp:70:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
met.cpp:74:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&req[i]);
                      ^
met.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
                ^
met.cpp:78:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&b[i].s,&b[i].e,&b[i].x);
                                          ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33664 KB Output is correct
2 Correct 3 ms 33664 KB Output is correct
3 Correct 6 ms 33664 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33664 KB Output is correct
2 Correct 6 ms 33664 KB Output is correct
3 Correct 3 ms 33664 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 34068 KB Output is correct
2 Correct 276 ms 34620 KB Output is correct
3 Correct 239 ms 34400 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 34296 KB Output is correct
2 Correct 226 ms 34312 KB Output is correct
3 Correct 289 ms 34692 KB Output is correct
4 Correct 49 ms 34464 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 34196 KB Output is correct
2 Correct 149 ms 34796 KB Output is correct
3 Correct 106 ms 33664 KB Output is correct
4 Correct 249 ms 34604 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 33956 KB Output is correct
2 Correct 229 ms 34320 KB Output is correct
3 Correct 189 ms 34060 KB Output is correct
4 Correct 276 ms 34816 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2679 ms 38452 KB Output is correct
2 Correct 819 ms 36316 KB Output is correct
3 Correct 569 ms 33664 KB Output is correct
4 Correct 3906 ms 43108 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2729 ms 38252 KB Output is correct
2 Correct 866 ms 35800 KB Output is correct
3 Correct 469 ms 33664 KB Output is correct
4 Correct 3616 ms 44344 KB Output is correct