結果
| 問題 | No.1074 増殖 |
| ユーザー |
 SSRS
|
| 提出日時 | 2020-06-05 22:46:01 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,526 bytes |
| コンパイル時間 | 2,164 ms |
| コンパイル使用メモリ | 185,744 KB |
| 実行使用メモリ | 12,500 KB |
| 最終ジャッジ日時 | 2024-12-17 16:52:11 |
| 合計ジャッジ時間 | 8,658 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 WA * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long INF = 1000000000;template <typename T>struct range_update_range_max{int N;vector<T> ST;vector<T> lazy;range_update_range_max(vector<T> A){int n = A.size();N = 1;while (N < n){N *= 2;}ST = vector<T>(N * 2 - 1, -INF);lazy = vector<T>(N * 2 - 1, -1);for (int i = 0; i < n; i++){ST[N - 1 + i] = A[i];}for (int i = N - 2; i >= 0; i--){ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);}}void eval(int i){if (lazy[i] != -1){if (i < N - 1){lazy[i * 2 + 1] = lazy[i];lazy[i * 2 + 2] = lazy[i];}ST[i] = lazy[i];lazy[i] = -1;}}void range_update(int L, int R, T x, int i, int l, int r){eval(i);if (R <= l || r <= L){return;} else if (L <= l && r <= R){lazy[i] = x;eval(i);} else {int m = (l + r) / 2;range_update(L, R, x, i * 2 + 1, l, m);range_update(L, R, x, i * 2 + 2, m, r);ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);}}void range_update(int L, int R, T x){return range_update(L, R, x, 0, 0, N);}T range_max(int L, int R, int i, int l, int r){eval(i);if (R <= l || r <= L){return -INF;} else if (L <= l && r <= R){return ST[i];} else {int m = (l + r) / 2;return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));}}T range_max(int L, int R){return range_max(L, R, 0, 0, N);}};template <typename T>struct range_update_range_sum{int N;vector<T> ST;vector<T> lazy;range_update_range_sum(int n){N = 1;while (N < n){N *= 2;}ST = vector<T>(N * 2 - 1, 0);lazy = vector<T>(N * 2 - 1, -1);}void eval(int i, int l, int r){if (lazy[i] != -1){if (i < N - 1){lazy[i * 2 + 1] = lazy[i];lazy[i * 2 + 2] = lazy[i];}ST[i] = lazy[i] * (r - l);lazy[i] = -1;}}void range_update(int L, int R, T x, int i, int l, int r){eval(i, l, r);if (R <= l || r <= L){return;} else if (L <= l && r <= R){lazy[i] = x;eval(i, l, r);} else {int m = (l + r) / 2;range_update(L, R, x, i * 2 + 1, l, m);range_update(L, R, x, i * 2 + 2, m, r);ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];}}void range_update(int L, int R, T x){range_update(L, R, x, 0, 0, N);}T range_sum(int L, int R, int i, int l, int r){eval(i, l, r);if (R <= l || r <= L){return 0;} else if (L <= l && r <= R){return ST[i];} else {int m = (l + r) / 2;return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r);}}T range_sum(int L, int R){return range_sum(L, R, 0, 0, N);}T operator [](int k){return range_sum(k, k + 1);}};int main(){int N;cin >> N;vector<int> Xa(N), Ya(N), Xb(N), Yb(N);for (int i = 0; i < N; i++){cin >> Xa[i] >> Ya[i] >> Xb[i] >> Yb[i];Xa[i] = -Xa[i];Ya[i] += 20000;Yb[i] += 20000;}range_update_range_max<long long> left1(vector<long long>(40000, 0)), right1(vector<long long>(40000, 0));range_update_range_sum<long long> left2(40000), right2(40000);for (int i = 0; i < N; i++){long long ans = 0;if (left1.range_max(Ya[i], Yb[i]) <= Xa[i]){ans += (Yb[i] - Ya[i]) * Xa[i] - left2.range_sum(Ya[i], Yb[i]);left1.range_update(Ya[i], Yb[i], Xa[i]);left2.range_update(Ya[i], Yb[i], Xa[i]);} else {//find max-pos//ternary searchint L = Ya[i] - 1;int R = Yb[i];while (R - L > 2){int mid1 = (L * 2 + R) / 3;int mid2 = (L + R * 2) / 3;if (left2[mid1] > left2[mid2]){R = mid2;} else {L = mid1;}}int pos = L;if (L + 1 < 40000){if (left2[L + 1] > left2[pos]){pos = L + 1;}}if (L + 2 < 40000){if (left2[L + 2] > left2[pos]){pos = L + 2;}}if (left2[Ya[i]] <= Xa[i]){//binary searchint tv = Ya[i];int fv = pos;while (fv - tv > 1){int mv = (tv + fv) / 2;if (left2[mv] <= Xa[i]){tv = mv;} else {fv = mv;}}ans += (fv - Ya[i]) * Xa[i] - left2.range_sum(Ya[i], fv);left1.range_update(Ya[i], fv, Xa[i]);left2.range_update(Ya[i], fv, Xa[i]);}if (left2[Yb[i] - 1] <= Xa[i]){//binary searchint tv = Yb[i] - 1;int fv = pos;while (tv - fv > 1){int mv = (tv + fv) / 2;if (left2[mv] <= Xa[i]){tv = mv;} else {fv = mv;}}ans += (Yb[i] - tv) * Xa[i] - left2.range_sum(tv, Yb[i]);left1.range_update(tv, Yb[i], Xa[i]);left2.range_update(tv, Yb[i], Xa[i]);}}if (right1.range_max(Ya[i], Yb[i]) <= Xb[i]){ans += (Yb[i] - Ya[i]) * Xb[i] - right2.range_sum(Ya[i], Yb[i]);right1.range_update(Ya[i], Yb[i], Xb[i]);right2.range_update(Ya[i], Yb[i], Xb[i]);} else {//find max-pos//ternary searchint L = Ya[i] - 1;int R = Yb[i];while (R - L > 2){int mid1 = (L * 2 + R) / 3;int mid2 = (L + R * 2) / 3;if (right2[mid1] > right2[mid2]){R = mid2;} else {L = mid1;}}int pos = L;if (L + 1 < 40000){if (right2[L + 1] > right2[pos]){pos = L + 1;}}if (L + 2 < 40000){if (right2[L + 2] > right2[pos]){pos = L + 2;}}if (right2[Ya[i]] <= Xb[i]){//binary searchint tv = Ya[i];int fv = pos;while (fv - tv > 1){int mv = (tv + fv) / 2;if (right2[mv] <= Xb[i]){tv = mv;} else {fv = mv;}}ans += (fv - Ya[i]) * Xb[i] - right2.range_sum(Ya[i], fv);right1.range_update(Ya[i], fv, Xb[i]);right2.range_update(Ya[i], fv, Xb[i]);}if (right2[Yb[i] - 1] <= Xb[i]){//binary searchint tv = Yb[i] - 1;int fv = pos;while (tv - fv > 1){int mv = (tv + fv) / 2;if (right2[mv] <= Xb[i]){tv = mv;} else {fv = mv;}}ans += (Yb[i] - tv) * Xb[i] - right2.range_sum(tv, Yb[i]);right1.range_update(tv, Yb[i], Xb[i]);right2.range_update(tv, Yb[i], Xb[i]);}}cout << ans << endl;}}