oj.uz

Submission #29316

# Submission time Handle Problem Language Result Execution time Memory
29316 2017-07-19T02:30:07 Z 서규호(#1166) Meteors (POI11_met) C++14
0 / 100
 0 ms 1856 KB 
#include <bits/stdc++.h>
#include <unistd.h>

#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define lld long long
#define Inf 1000000000
#define Mod 1000000007
#define Linf 1000000000000000000LL
#define get gett

using namespace std;

int bsize;
int N,M,K;
int a[300002],need[300002];
int x[300002],y[300002],z[300002];
lld cnt[550][300002];

int get(int it,int color){
    int tmp = 0;
    for(int i=1; i<=it; i++) if(color == a[i]) tmp++;
    return tmp;
}

int main(){
    //freopen("input.txt","r",stdin);
	scanf("%d %d",&N,&M);
	for(int i=1; i<=M; i++) scanf("%d",&a[i]);
	for(int i=1; i<=N; i++) scanf("%d",&need[i]);
	scanf("%d",&K); bsize = sqrt(K);
	for(int i=1; i<=K; i++){
		scanf("%d %d %d",&x[i],&y[i],&z[i]);
		if(x[i] <= y[i]){
			cnt[i/bsize][x[i]]+=z[i];
			cnt[i/bsize][y[i]+1]-=z[i];
		}else{
			cnt[i/bsize][1]+=z[i];
			cnt[i/bsize][y[i]+1]-=z[i];
			cnt[i/bsize][x[i]]+=z[i];
		}
	}
	for(int i=1/bsize; i<=K/bsize; i++){
		for(int j=1; j<=M; j++){
			cnt[i][j] += cnt[i][j-1];
			cnt[K/bsize+1][j] = cnt[i][j];
		}
		for(int j=1; j<=N; j++) cnt[i][j] = 0;
		for(int j=1; j<=M; j++){
			cnt[i][a[j]] += cnt[K/bsize+1][j];
			cnt[i][a[j]] = min(cnt[i][a[j]],(lld)Inf);
		}
	}
	for(int i=1; i<=N; i++){
		lld sum = 0;
		int s = 0,e;
		for(int j=1/bsize; j<=K/bsize; j++){
			sum += cnt[j][i];
			if(sum >= need[i]){
				s = max(1,j*bsize);
				e = min((j+1)*bsize-1,K);
				sum -= cnt[j][i];
				break;
			}
		}
		if(s == 0){
			puts("NIE");
			continue;
		}
        for(int j=s; j<=e; j++){
            lld tmp;
            if(x[j] <= y[j]){
                tmp = get(y[j],i)-get(x[j]-1,i);
            }else{
                tmp = get(y[j],i)+get(M,i)-get(x[j]-1,i);
            }
            sum += tmp*z[j];
            if(sum >= need[i]){
                printf("%d\n",j);
                break;
            }
        }
	}

	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:32:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
met.cpp:33:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=M; i++) scanf("%d",&a[i]);
                                           ^
met.cpp:34:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d",&need[i]);
                                              ^
met.cpp:35:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&K); bsize = sqrt(K);
                ^
met.cpp:37:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x[i],&y[i],&z[i]);
                                      ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -