oj.uz

Submission #29332

# Submission time Handle Problem Language Result Execution time Memory
29332 2017-07-19T02:49:08 Z 서규호(#1166) Meteors (POI11_met) C++14
0 / 100
 376 ms 63136 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;

const int bsize = 17000;
int N,M,K;
int a[300002],need[300002];
int x[300002],y[300002],z[300002];
lld cnt[(300000/bsize)+2][300002];
vector<int> memo[300002];

int get(int it,int color){
    int l,r,tmp;
    if(memo[color].size() == 0 || it < memo[color][0]) return 0;
    l = 0; r = memo[color].size()-1;
    while(l <= r){
        int m = (l+r)/2;
        if(it >= memo[color][m]){
            tmp = m+1;
            l = m+1;
        }else r = m-1;
    }

    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]);
        memo[a[i]].pb(i);
	}
	for(int i=1; i<=N; i++) scanf("%d",&need[i]);
	scanf("%d",&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);
            }*/
            tmp = 0;
            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:42: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:44:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
met.cpp:47: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:48:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&K);
                ^
met.cpp:50: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]);
                                      ^
met.cpp: In function 'int gett(int, int)':
met.cpp:26:13: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int l,r,tmp;
             ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 59440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 59440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 59704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 59836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 59836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 59732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 376 ms 63136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 63008 KB Output isn't correct
2 Halted 0 ms 0 KB -