結果

問題 No.1074 増殖
ユーザー chocopuuchocopuu
提出日時 2020-06-06 03:57:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 181 ms / 2,000 ms
コード長 1,968 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 219,548 KB
実行使用メモリ 8,548 KB
最終ジャッジ日時 2024-06-01 08:08:19
合計ジャッジ時間 5,055 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 124 ms
7,780 KB
testcase_07 AC 167 ms
8,548 KB
testcase_08 AC 149 ms
8,420 KB
testcase_09 AC 148 ms
7,652 KB
testcase_10 AC 120 ms
7,524 KB
testcase_11 AC 119 ms
7,652 KB
testcase_12 AC 120 ms
7,648 KB
testcase_13 AC 181 ms
7,652 KB
testcase_14 AC 179 ms
7,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define int long long
using i64 = long long;
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e18;



signed main() {
	i64 N;
	cin >> N;
	vector<i64>xa(N), ya(N), xb(N), yb(N);
	REP(i, N) {
		cin >> xa[i] >> ya[i] >> xb[i] >> yb[i];
	}
	vector<i64> ans(N);
	auto func = [&](vector<i64>&x, vector<i64>&y) -> void {
		set<pair<i64,i64>>st;
		st.insert({INF, 0});
		st.insert({0, INF});
		REP(i, N) {
			vector<pair<i64,i64>>tmp;
			auto itr = st.upper_bound({x[i], -INF});
			while(1){
				tmp.emplace_back(*itr);
				--itr;
				if(tmp.back().second >= y[i])break;
			}
			REP(j,tmp.size())st.erase(tmp[j]);
			int t = tmp[0].first;
			tmp[0].first = x[i];
			i64 sum = 0;
			REP(j, tmp.size() - 1) {
				//out(i,tmp[j].first,tmp[j + 1].first,tmp[j].second);
				ans[i] += (tmp[j].first - tmp[j + 1].first) * (y[i] - tmp[j].second);
			}
			tmp[0].first = t;
			if(tmp.size() == 1)st.insert(tmp[0]);
			else{
				if(tmp[0].first != x[i])st.insert(tmp[0]);
				st.insert({x[i],y[i]});
				st.insert(tmp.back());
			}
		}
	};
	vector<vector<i64>>x(4,vector<i64>(N)),y(4,vector<i64>(N));
	REP(i, N) {
		x[0][i] = -xa[i], y[0][i] = -ya[i];
		x[1][i] = -xa[i], y[1][i] = yb[i];
		x[2][i] = xb[i], y[2][i] = -ya[i];
		x[3][i] = xb[i], y[3][i] = yb[i];
	}
	//func(x[3], y[3]);
	REP(i, 4) func(x[i], y[i]);
	REP(i, N) cout << ans[i] << endl;
}
0