oj.uz

Submission #232849

# Submission time Handle Problem Language Result Execution time Memory
232849 2020-05-18T11:10:57 Z shayan_p Raspad (COI17_raspad) C++14
100 / 100
 1228 ms 545592 KB 
// Never let them see you bleed...
 
#include<bits/stdc++.h>
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 1e5 + 10, MAX = 26, mod = 1e9 + 7, inf = 1e9 + 10;
 
ll MSK[maxn];
ll vec[maxn][MAX][MAX], arr[MAX];
int ID[maxn][MAX];
 
int n, m;
 
int origin(int i){ ///////
    ll msk = 0;
    int cnt = 0;
    for(int j = 0; j < m; j++){
	if(bit(MSK[i], j))
	    msk|= 1ll<<j;
	if(bit(MSK[i], j) && !bit(MSK[i], j+1))
	    arr[cnt++] = msk, msk = 0;
    }
    memcpy(vec[i][cnt], arr, sizeof arr);
    ID[i][cnt] = i;
 
    return cnt;
}
 
int aft[66], bef[66], col[66], colId;
ll _MSK;
 
void dfs(int u){
    col[u] = colId;
    arr[colId]|= 1ll<<u;
    if(bef[u] != -1 && col[bef[u]] == -1)
	dfs(bef[u]);
    if(aft[u] != -1 && col[aft[u]] == -1)
	dfs(aft[u]);
    if(u != 0 && bit(_MSK, u-1) && col[u-1] == -1)
	dfs(u-1);
    if(bit(_MSK, u+1) && col[u+1] == -1)
	dfs(u+1);
}
 
int mrg(int id, ll *ARR, int SZ, int _ID){ //////
    memset(aft, -1, sizeof aft);
    memset(bef, -1, sizeof bef);
    memset(col, -1, sizeof col);
    memset(arr, 0, sizeof arr);    
    colId = 0;
    _MSK = MSK[id];    
    for(int i = 0; i < SZ; i++){
	ll msk = MSK[id] & ARR[i];
	int bf = -1;
	while(msk){
	    int nw = __builtin_ctzll(msk);
	    msk^= 1ll<<nw;
	    if(bf != -1)
		bef[nw] = bf, aft[bf] = nw;
	    bf = nw;
	}
    }
    for(int i = 0; i < m; i++){
	if(col[i] == -1 && bit(_MSK, i)){
	    dfs(i);
	    colId++;
	}		    
    }
    if(ID[id][colId] == -1){
	ID[id][colId] = _ID;
	memcpy(vec[id][colId], arr, sizeof arr);
    }
 
    return colId;    
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
 
    memset(ID, -1, sizeof ID);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
	string s;
	cin >> s;
	for(int j = 0; j < m; j++)
	    MSK[i]|= (1ll * (s[j] == '1')) << j;
    }
    origin(0);
    for(int i = 1; i < n; i++){
	origin(i);
	for(int j = MAX-1; j >= 0; j--){
	    if(ID[i-1][j] == -1)
		continue;
	    mrg(i, vec[i-1][j], j, ID[i-1][j]);	    
	}
    }

    ll ans = 0;

    for(int i = 0; i < n; i++){
	if(MSK[i] == 0)
	    continue;
	int mx = -1;
	for(int j = 1; j < MAX; j++){
	    if(ID[i][j] == -1)
		continue;
	    for(int k = 0; k < j; k++){
		int cof = 1;
		if((MSK[i+1] & vec[i][j][k]) == 0)
		    cof = n-i;
		ans+= 1ll * cof * (ID[i][j] - mx);
	    }
	    mx = max(mx, ID[i][j]);
	}
    }
    return cout << ans << endl, 0;    
    /*

    for(int l = 0; l < n; l++){
	int num = 0, comp = 0;
	for(int r = l; r < n; r++){
	    if(l != r){
		for(int i = 0; i < comp; i++)
		    if((vec[r-1][comp][i] & MSK[r]) != 0)
			num--;
	    }
	    comp = -1;
	    for(int i = MAX-1; i >= 0; i--)
		if(ID[r][i] >= l)
		    comp = i;
	    num+= comp;
	    ans+= num;
	}
    }
    return cout << ans << endl, 0;*/
    
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 12 ms 11008 KB Output is correct
3 Correct 9 ms 11008 KB Output is correct
4 Correct 9 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 11008 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 12 ms 11008 KB Output is correct
3 Correct 9 ms 11008 KB Output is correct
4 Correct 9 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 11008 KB Output is correct
7 Correct 12 ms 14336 KB Output is correct
8 Correct 10 ms 12672 KB Output is correct
9 Correct 18 ms 15616 KB Output is correct
10 Correct 12 ms 15232 KB Output is correct
11 Correct 14 ms 15232 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 13 ms 14976 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 220920 KB Output is correct
2 Correct 251 ms 432968 KB Output is correct
3 Correct 326 ms 462332 KB Output is correct
4 Correct 217 ms 390392 KB Output is correct
5 Correct 85 ms 138360 KB Output is correct
6 Correct 265 ms 443128 KB Output is correct
7 Correct 319 ms 491256 KB Output is correct
8 Correct 211 ms 358776 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 12 ms 11008 KB Output is correct
3 Correct 9 ms 11008 KB Output is correct
4 Correct 9 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 11008 KB Output is correct
7 Correct 12 ms 14336 KB Output is correct
8 Correct 10 ms 12672 KB Output is correct
9 Correct 18 ms 15616 KB Output is correct
10 Correct 12 ms 15232 KB Output is correct
11 Correct 14 ms 15232 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 13 ms 14976 KB Output is correct
14 Correct 118 ms 220920 KB Output is correct
15 Correct 251 ms 432968 KB Output is correct
16 Correct 326 ms 462332 KB Output is correct
17 Correct 217 ms 390392 KB Output is correct
18 Correct 85 ms 138360 KB Output is correct
19 Correct 265 ms 443128 KB Output is correct
20 Correct 319 ms 491256 KB Output is correct
21 Correct 211 ms 358776 KB Output is correct
22 Correct 287 ms 362484 KB Output is correct
23 Correct 786 ms 537592 KB Output is correct
24 Correct 738 ms 542840 KB Output is correct
25 Correct 320 ms 447864 KB Output is correct
26 Correct 362 ms 545400 KB Output is correct
27 Correct 378 ms 465912 KB Output is correct
28 Correct 663 ms 529272 KB Output is correct
29 Correct 413 ms 464764 KB Output is correct
30 Correct 274 ms 436088 KB Output is correct
31 Correct 1228 ms 545592 KB Output is correct
32 Correct 703 ms 524536 KB Output is correct
33 Correct 452 ms 457208 KB Output is correct
34 Correct 530 ms 467704 KB Output is correct