oj.uz

Submission #26294

# Submission time Handle Problem Language Result Execution time Memory
26294 2017-06-29T05:47:58 Z 서규호(#1103) Raspad (COI17_raspad) C++14
0 / 100
 153 ms 66088 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define Inf 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,nn; lld ans;
int a[100002][52];
int where[100002][52],when[100002][52];
char s[100];
lld seg[400002];

void update(int node,int l,int r,int s,int e,lld value){
	if(r < s || e < l || s > e) return;
	if(s <= l && r <= e){
		seg[node] += (value*(r-l+1));
		return;
	}
	int mid = (l+r)/2;
	update(node*2,l,mid,s,e,value);
	update(node*2+1,mid+1,r,s,e,value);
	seg[node] = seg[node*2]+seg[node*2+1];
}

int main(){
	scanf("%d %d",&N,&M);
	for(nn=1; nn<N; nn*=2);
	for(int i=1; i<=N; i++){
		scanf("%s",s);
		for(int j=1; j<=M; j++) a[i][j] = s[j-1]-'0';
	}
	for(int i=1; i<=N; i++){
		vector<pp> tmp;
		bool flag = false;
		for(int j=1; j<=M+1; j++){
			if(!flag && a[i][j] == 1){
				flag = true;
				tmp.pb({j,0});
			}
			if(flag && a[i][j] == 0){
				flag = false;
				tmp.back().second = j-1;
			}
		}
		update(1,1,nn,i,i,tmp.size());
		vector<pp> memo;
		for(int j=0; j<tmp.size(); j++){
			int s,e;
			s = tmp[j].first; e = tmp[j].second;
			vector<int> t;
			for(int k=s; k<=e; k++){
				where[i][k] = j+1;
				if(a[i-1][k] == 1){
					if(t.size() == 0) t.pb(where[i-1][k]);
					else if(t.back() != where[i-1][k]) t.pb(where[i-1][k]);
				}
			}
			if(t.size() == 0){
				update(1,1,nn,1,i-1,1);
				memo.pb({-1,-1});
			}else{
				memo.pb({t[0],t.back()});
			}
			for(int k=0; k<(int)t.size()-1; k++){
				if(when[i-1][t[k]] == Inf){
                    update(1,1,nn,1,i-1,-1);
				}else{
                    update(1,1,nn,when[i-1][t[k]]+1,i-1,-1);
				}
			}
		}
		for(int j=0; j<(int)tmp.size()-1; j++){
			if(memo[j].first == -1 || memo[j+1].first == -1){
				when[i][j+1] = Inf;
				continue;
			}
			if(memo[j].second >= memo[j+1].first){
				when[i][j+1] = i-1;
			}
			for(int k=memo[j].second; k<memo[j+1].first; k++){
				when[i][j+1] = max(when[i][j+1],when[i-1][k]);
			}
		}
		ans += seg[1];
	}
	printf("%lld\n",ans);

	return 0;
}

Compilation message

raspad.cpp: In function 'int main()':
raspad.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<tmp.size(); j++){
                 ^
raspad.cpp:35:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
raspad.cpp:38:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
                ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66088 KB Output is correct
2 Incorrect 153 ms 66088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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