Submission #1061762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061762		Matthewwww	Nafta (COI15_nafta)	C++17	0 / 100	3 ms	3676 KiB

nafta

bool DEBUG
#ifdef LOCAL
= true;
#include <bits/stdc++.h>
#include <atcoder/all>
#include <local/debug>
#define nyoom 69
#define freopen(...) 69
#else
;
#include <bits/stdc++.h>
#define debug(x) x
#define dbg(x, y) x
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#define nyoom ios_base::sync_with_stdio(false); cin.tie(nullptr)
#endif
#ifdef ATCODER
#include <atcoder/all>
using namespace atcoder;
#endif
#define int long long
#define all(x) x.begin(), x.end()
#define err if (DEBUG) cout
#define f first
#define s second
using namespace std;

const int dir[5] = {0, 1, 0, -1, 0};

int n, m;

int stuff[2001][2001];

#define eval(x, y) (~x.first ? x.second - stuff[x.first][y] : 0ll)

struct Clm{
	int tl, tm, tr;
	pair<pair<int, int>, int> f; // left point then constant
	Clm *lft = nullptr, *rht = nullptr;
	Clm (int l, int r, pair<pair<int, int>, int> a): tl(l), tr(r), f(a), tm(l+r>>1){}
	void update (pair<pair<int, int>, int> nw){
		if (eval(nw.f, tm) > eval(f.f, tm))
			swap(nw, f);
		if (tl+1 == tr)
			return;
		if (nw.f.f > f.f.f){
			if (!rht)
				rht = new Clm(tl, tm, nw);
			else
				rht->update(nw);
		} else {
			if (!lft)
				lft = new Clm(tm, tr, nw);
			else 
				lft->update(nw);
		}
	}
	pair<int, int> query (int x){
		if (x < tm)
			return lft ? max(lft->query(x), {eval(f.f, x), f.s}) : make_pair(eval(f.f, x), f.s);
		return rht ? max(rht->query(x), {eval(f.f, x), f.s}) : make_pair(eval(f.f, x), f.s);
	}
};

struct Sgt{
	int tl, tr, val = 0;
	Sgt *lft, *rht;
	Sgt (int l, int r): tl(l), tr(r){
		if (tl != tr-1){
			int tm = tl+tr>>1;
			lft = new Sgt(tl, tm);
			rht = new Sgt(tm, tr);
		}
	}
	void update (int i, int x){
		if (tl == tr-1){
			val += x;
			return;
		}
		(i < lft->tr ? lft : rht)->update(i, x);
		val = lft->val+rht->val;
	}
	int query (int l){
		if (l >= tr)
			return 0;
		if (l <= tl)
			return val;
		return lft->query(l)+rht->query(l);
	}
};

void dfs (int i, int j, vector<vector<int>> &grid, vector<pair<pair<int, int>, int>> &loose){
	if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '.'-'0')
		return;
	loose.back().s += grid[i][j];
	grid[i][j] = '.'-'0';
	loose.back().f.s = max(loose.back().f.s, j);
	loose.back().f.f = min(loose.back().f.f, j);
	for (int k = 0; k < 4; k++)
		dfs(i+dir[k], j+dir[k+1], grid, loose);
}

int active[2001];

pair<int, int> solve (int punish){
	Clm lct(0, m, {{-1, 0}, 0});
	pair<int, int> dp[m];
	for (int i = 0; i < m; i++){
		auto res = lct.query(i);
		dp[i].f = res.f+active[i]-punish;
		dp[i].s = res.s-1;
		lct.update({{i, dp[i].f}, dp[i].s});
	}
	pair<int, int> best = {0, 0};
	for (auto i : dp)
		best = max(best, {i.f-i.s*punish, i.s});
	dbg(dp, m);
	return {best.f, -best.s};
}

signed main(){
	nyoom;
	cin >> n >> m;
	vector<vector<int>> grid(n, vector<int>(m));
	vector<pair<pair<int, int>, int>> ranges;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			char a;
			cin >> a;
			grid[i][j] = a-'0';
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (grid[i][j] != '.'-'0'){
				ranges.push_back({{INT_MAX, INT_MIN}, 0});
				dfs(i, j, grid, ranges);
			}
		}
	}
	sort(ranges.begin(), ranges.end());
	int ptr = 0;
	for (auto i : ranges){
		active[i.f.f] += i.s;
		active[i.f.s+1] -= i.s;
	}
	dbg(active, m+1);
	for (int i = 0; i < m; i++)
		active[i+1] += active[i];
	Sgt sgt(0, m);
	for (int i = 0; i < m; i++){
		while (ptr < ranges.size() && ranges[ptr].f.f == i){
			sgt.update(ranges[ptr].f.s, ranges[ptr].s);
			++ptr;
		}
		for (int j = i; j < m; j++)
			stuff[i][j] = sgt.query(j);
		for (int j = 0; j < i; j++)
			stuff[i][j] = INT_MAX;
	}
	debug(solve(2));
	debug(ranges);
	dbg(active, m);
	for (int i = 0; i < m; i++){
		for (int j = 0; j < m; j++)
			err << stuff[i][j] << " ";
		err << "\n";
	}
	
	for (int i = 1; i <= m; i++){
		int ans = -1;
		for (int k = 25; k--;)
			if (solve(ans+(1<<k)).s > i)
				ans += (1<<k);
		cout << solve(ans+1).f << "\n";
	}
	
}



#undef int
#undef all
#undef err
#undef f
#undef s

/*
*
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃   ━   ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃   ┻   ┃ 
* ┗━┓   ┏━┛  + + 
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the llama protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*   ┃        ┏┛
*   ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

//thanks cindy

Compilation message (stderr)

nafta.cpp: In constructor 'Clm::Clm(long long int, long long int, std::pair<std::pair<long long int, long long int>, long long int>)':
nafta.cpp:41:75: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  Clm (int l, int r, pair<pair<int, int>, int> a): tl(l), tr(r), f(a), tm(l+r>>1){}
      |                                                                          ~^~
nafta.cpp:25:11: warning: 'Clm::first' will be initialized after [-Wreorder]
   25 | #define f first
      |           ^~~~~
nafta.cpp:39:28: note: in expansion of macro 'f'
   39 |  pair<pair<int, int>, int> f; // left point then constant
      |                            ^
nafta.cpp:38:10: warning:   'long long int Clm::tm' [-Wreorder]
   38 |  int tl, tm, tr;
      |          ^~
nafta.cpp:41:2: warning:   when initialized here [-Wreorder]
   41 |  Clm (int l, int r, pair<pair<int, int>, int> a): tl(l), tr(r), f(a), tm(l+r>>1){}
      |  ^~~
nafta.cpp: In constructor 'Sgt::Sgt(long long int, long long int)':
nafta.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |    int tm = tl+tr>>1;
      |             ~~^~~
nafta.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
nafta.cpp:118:6: warning: statement has no effect [-Wunused-value]
  118 |  dbg(dp, m);
      |      ^~
nafta.cpp:13:19: note: in definition of macro 'dbg'
   13 | #define dbg(x, y) x
      |                   ^
nafta.cpp: In function 'int main()':
nafta.cpp:148:6: warning: statement has no effect [-Wunused-value]
  148 |  dbg(active, m+1);
      |      ^~~~~~
nafta.cpp:13:19: note: in definition of macro 'dbg'
   13 | #define dbg(x, y) x
      |                   ^
nafta.cpp:153:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   while (ptr < ranges.size() && ranges[ptr].f.f == i){
      |          ~~~~^~~~~~~~~~~~~~~
nafta.cpp:163:8: warning: statement has no effect [-Wunused-value]
  163 |  debug(ranges);
      |        ^~~~~~
nafta.cpp:12:18: note: in definition of macro 'debug'
   12 | #define debug(x) x
      |                  ^
nafta.cpp:164:6: warning: statement has no effect [-Wunused-value]
  164 |  dbg(active, m);
      |      ^~~~~~
nafta.cpp:13:19: note: in definition of macro 'dbg'
   13 | #define dbg(x, y) x
      |                   ^

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