Submission #932497

#	Time	Username	Problem	Language	Result	Execution time	Memory
932497		idiotcomputer	Nafta (COI15_nafta)	C++11	34 / 100	90 ms	68208 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first 
#define s second
#define pb push_back
 
const int mxN = 4*1e6;
const int mxS = 2000;
int R,S;
int sums[mxN];
pii bounds[mxN];
int grid[mxN];
int vis[mxN];
int has[mxN];
 
int cnt = 0;
void bfs(int node){
    queue<int> queue;
    queue.push(node);
    int curr,r,s;
    bounds[cnt].f = mxS+1;
    bounds[cnt].s = -1;
    while (queue.size() > 0){
        curr = queue.front();
        queue.pop();
        if (vis[curr] != -1 || grid[curr] == -1){
            continue;
        }
        vis[curr] = cnt;
        sums[cnt] += grid[curr];
        r = curr / S;
        s = curr % S;
        bounds[cnt].f = min(bounds[cnt].f, s);
        bounds[cnt].s = max(bounds[cnt].s, s);
        if (r > 0){
            queue.push(curr - S);  
        } 
        if (r < R-1){
            queue.push(curr+S);
        }
        if (s > 0){
            queue.push(curr-1);
        }
        if (s < S-1){
            queue.push(curr+1);
        }
    }
    cnt++;
}
 
 
int res[mxS];
int tres[mxS];
int segtree[4*mxS+1];
int laz[4*mxS+1];
 
void build(int l = 0, int r = S-1, int idx = 0){
    laz[idx] = 0;
    if (l == r){
        segtree[idx] = res[l];
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    segtree[idx] = max(segtree[2*idx+1],segtree[2*idx+2]);
}
 
void upd(int tl, int tr, int v, int l = 0, int r = S-1, int idx = 0){
    if (tr < tl){
        return;
    }
    if (l > tr || r < tl){
        return;
    }
    if (l >= tl && r <= tr){
        laz[idx] += v;
        return;
    }
    int m = (l+r)/2;
    upd(tl,tr,v,l,m,2*idx+1);
    upd(tl,tr,v,m+1,r,2*idx+2);
    segtree[idx] = max(laz[2*idx+1] + segtree[2*idx+1],laz[2*idx+2] + segtree[2*idx+2]);
}
 
int query(int tl, int tr, int l = 0, int r = S-1, int idx = 0){
    if (l > tr || r < tl){
        return -1;
    }
    if (l >= tl && r <= tr){
        return segtree[idx] + laz[idx];
    }
    int m = (l+r)/2;
    return laz[idx] + max(query(tl,tr,l,m,2*idx+1),query(tl,tr,m+1,r,2*idx+2));
}
 
int main()
{
    memset(sums,0,sizeof(sums));
    
    for (int i =0; i < mxN; i++){
        has[i] = -1;
        vis[i] = -1;
    }
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> R >> S; 
    
    string row;
    for (int i =0; i < R; i++){
        cin >> row;
        for (int j =0; j < S; j++){
            if (row[j] == '.'){
                grid[i*S+j] = -1;
            } else {
                grid[i*S+j] = row[j]-'0';
            }
        }    
    }
    for (int i = 0; i < R*S; i++){
        if (vis[i] == -1 && grid[i] != -1){
            bfs(i);
        }
    }
    for (int i =0; i < cnt; i++){
        if (has[bounds[i].f*S + bounds[i].s] == -1){
            has[bounds[i].f*S + bounds[i].s] = i;
        } else {
            sums[has[bounds[i].f*S + bounds[i].s]] += sums[i];
        }
    }
    

    vector<vector<int>> cont(S);
    vector<vector<int>> beg(S);
    vector<vector<int>> en(S);
    memset(res,0,sizeof(res));
    int currc = 0;
    for (int i =0; i < cnt; i++){
        if (has[bounds[i].f*S + bounds[i].s] != i){
            continue;
        }
        currc += 1;
        beg[bounds[i].f].pb(i);
        en[bounds[i].s].pb(i);
        res[bounds[i].f] += sums[i];
        if (bounds[i].s != bounds[i].f){
            res[bounds[i].s] += sums[i];
        }
        for (int j = bounds[i].f+1; j < bounds[i].s; j++){
            cont[j].pb(i);
            res[j] += sums[i];
        }
    }
    if (currc >= 4000){
        return 0;
    }
    int tot = 0;
    for (int i =0; i < S; i++){
        tot = max(tot,res[i]);
    }
    cout << tot << '\n';
    for (int i = 1; i < S; i++){
        memset(tres,0,sizeof(tres));
        build();
        tot = 0;
        for (int v : cont[i]){
            upd(0,bounds[v].f-1,sums[v]);
        }
        for (int j = i; j < S; j++){
            for (int v : beg[j]){
                upd(0,bounds[v].f-1,sums[v]);
            }
            tres[j] = query(0,j-1);
            tot = max(tot, tres[j]);
            for (int v : en[j]){
                upd(0,bounds[v].f-1,-1*sums[v]);
            }
        }  
        cout << tot << '\n';
        swap(tres,res);
    }
    
    
    
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66