Submission #156054

#	Time	Username	Problem	Language	Result	Execution time	Memory
156054		rdd6584	조개 줍기 (KOI17_shell)	C++14	0 / 100	222 ms	23800 KiB

shell

#include <cstdio>
#include <memory.h>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <iostream>
#include <set>
#include <list>
#include <map>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

priority_queue<int, vector<int>, greater<int> > pq;
vector<int> v;

int lazy[1501][4096];
int szz = 1;

void update(int d, int i, int l, int r, int le, int ri, int val) {
	if (l > ri || r < le) return;
	if (l <= le && ri <= r) {
		lazy[d][i] += val;
		return;
	}
	update(d, i * 2, l, r, le, (le + ri) / 2, val);
	update(d, i * 2 + 1, l, r, (le + ri) / 2 + 1, ri, val);
}

int find(int d, int i) {
	i += szz;

	int sum = 0;
	while (i) {
		sum += lazy[d][i];
		i /= 2;
	}

	return sum;
}

pii vec[1501];
int dx[2] = { 0, 1 }, dy[2] = { 1, 0 };
int n, ty;

void go(int x, int y, int st) {
	vec[x].first = min(vec[x].first, y);
	vec[x].second = max(vec[x].second, y);

	for (int i = 0; i < 2; i++) {
		int xx = x + dx[i ^ st], yy = y + dy[i ^ st];
		if (xx > n || yy > n) continue;

		int ax = xx + dx[i ^ st ^ 1] * -1, ay = yy + dy[i ^ st ^ 1] * -1;
		if (find(x, y) + ty < find(ax, ay)) continue;
		go(xx, yy, st);
	}
}

int main() {
	scanf("%d", &n);
	while (szz <= n) szz *= 2;

	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int t;
			scanf("%d", &t);
			lazy[i][j + szz] += max(lazy[i - 1][j + szz], lazy[i][j + szz - 1]) + t;
			ans += lazy[i][j + szz];
		}
	}

	printf("%lld\n", ans);
	for (int i = 0; i < n; i++) {
		char a;
		int b, c;
		scanf(" %c %d %d", &a, &b, &c);

		if (a == 'U') ty = 0;
		else ty = -1;

		// 최소최대.
		for (int j = 1; j <= n; j++)
			vec[j] = { (int)2e9, -1 };

		go(b, c, 0);
		if (ty == 0) ty++;

		for (int j = 1; j <= n; j++) {
			if (vec[j].first > vec[j].second) continue;
			update(j, 1, vec[j].first, vec[j].second, 0, szz - 1, ty);
			ans += (vec[j].second - vec[j].first + 1) * ty;
		}

		assert(lazy[b][c + szz] >= 0);
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shell.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~
shell.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 34
• Subtask 3: 0 / 54