oj.uz

Submission #156054

# Submission time Handle Problem Language Result Execution time Memory
156054 2019-10-03T03:42:20 Z rdd6584 None (KOI17_shell) C++14
0 / 100
 222 ms 23800 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -