結果
| 問題 | No.1074 増殖 |
| ユーザー |
 noimi
|
| 提出日時 | 2020-06-05 21:50:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 214 ms / 2,000 ms |
| コード長 | 12,988 bytes |
| コンパイル時間 | 4,346 ms |
| コンパイル使用メモリ | 235,752 KB |
| 最終ジャッジ日時 | 2025-01-10 22:28:08 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 |
コンパイルメッセージ
main.cpp:412:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
412 | main(){
| ^~~~
main.cpp: In function ‘void scan(char*)’:
main.cpp:52:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
52 | void scan(char a[]){ scanf("%s", a); }
| ~~~~~^~~~~~~~~
ソースコード
#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i>=b;--i)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vec vector<int>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define overload2(_1,_2,name,...) name
#define vv(a,b) vector<vector<int>>(a,vector<int>(b))
#define vv2(a,b,c) vector<vector<int>>(a,vector<int>(b,c))
#define vvl(a,b) vector<vector<ll>>(a,vector<ll>(b))
#define vvl2(a,b,c) vector<vector<ll>>(a,vector<ll>(b,c))
#define vvv(a,b,c) vector<vv(b,c)>(a)
#define vvv2(a,b,c,d) vector<vv(b,c,d)>(a)
#define vvvl(a,b,c) vector<vvl(b,c)>(a)
#define vvvl2(a,b,c,d) vector<vvl(b,c,d)>(a)
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance((c).begin(),lower_bound(all(c),(x)))
#define ub(c,x) distance((c).begin(),upper_bound(all(c),(x)))
using namespace std;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
#define Size(c) (int)(c).size()
#define INT(...) int __VA_ARGS__;IN(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;IN(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;IN(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;IN(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;IN(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;IN(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;IN(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);IN(name)
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));IN(name)
int scan(){ return getchar(); }
void scan(int& a){ cin>>a; }
void scan(long long& a){ cin>>a; }
void scan(char &a){cin>>a;}
void scan(double &a){ cin>>a; }
void scan(long double& a){ cin>>a; }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void IN(){}
template <class Head, class... Tail> void IN(Head& head, Tail&... tail){ scan(head); IN(tail...); }
string stin() {string s;cin>>s;return s;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
vi iota(int n){vi a(n);iota(all(a),0);return a;}
template<class T> void UNIQUE(vector<T> &x){sort(all(x));x.erase(unique(all(x)),x.end());}
int in() {int x;cin>>x;return x;}
ll lin() {unsigned long long x;cin>>x;return x;}
void print(){putchar(' ');}
void print(bool a){cout<<a;}
void print(int a){cout<<a;}
void print(long long a){cout<<a;}
void print(char a){cout<<a;}
void print(string &a){cout<<a;}
void print(double a){cout<<a;}
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } cout<<endl;}
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ cout<<'(';print(p.first); cout<<","; print(p.second);cout<<')'; }
template<class T> void print(set<T> &x){for(auto e:x)print(e),cout<<" ";cout<<endl;}
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ cout<<" "; print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
ll gcd(ll a, ll b){ a = abs(a),b = abs(b);while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
vector<pll> factor(ll x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
vector<int> divisor(int x){ vector<int> ans; for(int i=1;i*i<=x;i++)if(x%i==0){ans.pb(i);if(i*i!=x)ans.pb(x/i);} return ans;}
int popcount(ll x){return __builtin_popcountll(x);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n){return uniform_int_distribution<int>(0, n-1)(rng);}
#define endl '\n'
#ifdef _LOCAL
#undef endl
#define debug(x) cout<<#x<<": ";print(x);cout<<endl;
void err(){}
template<class T> void err(const T& t){ print(t); cout<<" ";}
template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }
#else
#define debug(x)
template<class... T> void err(const T&...){}
#endif
struct Setup_io{ Setup_io(){ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);}}setup_io;
#pragma endregion
// _______ここから編集！_______________
constexpr int N = 40010;
class SegmentTree {
const ll inf = 1e18;
int n, n0;
ll max_v[4*N], smax_v[4*N], max_c[4*N];
ll min_v[4*N], smin_v[4*N], min_c[4*N];
ll sum[4*N];
ll len[4*N], ladd[4*N], lval[4*N];
void update_node_max(int k, ll x) {
sum[k] += (x - max_v[k]) * max_c[k];
if(max_v[k] == min_v[k]) {
max_v[k] = min_v[k] = x;
} else if(max_v[k] == smin_v[k]) {
max_v[k] = smin_v[k] = x;
} else {
max_v[k] = x;
}
if(lval[k] != inf && x < lval[k]) {
lval[k] = x;
}
}
void update_node_min(int k, ll x) {
sum[k] += (x - min_v[k]) * min_c[k];
if(max_v[k] == min_v[k]) {
max_v[k] = min_v[k] = x;
} else if(smax_v[k] == min_v[k]) {
min_v[k] = smax_v[k] = x;
} else {
min_v[k] = x;
}
if(lval[k] != inf && lval[k] < x) {
lval[k] = x;
}
}
void push(int k) {
if(n0-1 <= k) return;
if(lval[k] != inf) {
updateall(2*k+1, lval[k]);
updateall(2*k+2, lval[k]);
lval[k] = inf;
return;
}
if(ladd[k] != 0) {
addall(2*k+1, ladd[k]);
addall(2*k+2, ladd[k]);
ladd[k] = 0;
}
if(max_v[k] < max_v[2*k+1]) {
update_node_max(2*k+1, max_v[k]);
}
if(min_v[2*k+1] < min_v[k]) {
update_node_min(2*k+1, min_v[k]);
}
if(max_v[k] < max_v[2*k+2]) {
update_node_max(2*k+2, max_v[k]);
}
if(min_v[2*k+2] < min_v[k]) {
update_node_min(2*k+2, min_v[k]);
}
}
void update(int k) {
sum[k] = sum[2*k+1] + sum[2*k+2];
if(max_v[2*k+1] < max_v[2*k+2]) {
max_v[k] = max_v[2*k+2];
max_c[k] = max_c[2*k+2];
smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]);
} else if(max_v[2*k+1] > max_v[2*k+2]) {
max_v[k] = max_v[2*k+1];
max_c[k] = max_c[2*k+1];
smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]);
} else {
max_v[k] = max_v[2*k+1];
max_c[k] = max_c[2*k+1] + max_c[2*k+2];
smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]);
}
if(min_v[2*k+1] < min_v[2*k+2]) {
min_v[k] = min_v[2*k+1];
min_c[k] = min_c[2*k+1];
smin_v[k] = min(smin_v[2*k+1], min_v[2*k+2]);
} else if(min_v[2*k+1] > min_v[2*k+2]) {
min_v[k] = min_v[2*k+2];
min_c[k] = min_c[2*k+2];
smin_v[k] = min(min_v[2*k+1], smin_v[2*k+2]);
} else {
min_v[k] = min_v[2*k+1];
min_c[k] = min_c[2*k+1] + min_c[2*k+2];
smin_v[k] = min(smin_v[2*k+1], smin_v[2*k+2]);
}
}
void _update_min(ll x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a || max_v[k] <= x) {
return;
}
if(a <= l && r <= b && smax_v[k] < x) {
update_node_max(k, x);
return;
}
push(k);
_update_min(x, a, b, 2*k+1, l, (l+r)/2);
_update_min(x, a, b, 2*k+2, (l+r)/2, r);
update(k);
}
void _update_max(ll x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a || x <= min_v[k]) {
return;
}
if(a <= l && r <= b && x < smin_v[k]) {
update_node_min(k, x);
return;
}
push(k);
_update_max(x, a, b, 2*k+1, l, (l+r)/2);
_update_max(x, a, b, 2*k+2, (l+r)/2, r);
update(k);
}
void addall(int k, ll x) {
max_v[k] += x;
if(smax_v[k] != -inf) smax_v[k] += x;
min_v[k] += x;
if(smin_v[k] != inf) smin_v[k] += x;
sum[k] += len[k] * x;
if(lval[k] != inf) {
lval[k] += x;
} else {
ladd[k] += x;
}
}
void updateall(int k, ll x) {
max_v[k] = x; smax_v[k] = -inf;
min_v[k] = x; smin_v[k] = inf;
max_c[k] = min_c[k] = len[k];
sum[k] = x * len[k];
lval[k] = x; ladd[k] = 0;
}
void _add_val(ll x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return;
}
if(a <= l && r <= b) {
addall(k, x);
return;
}
push(k);
_add_val(x, a, b, 2*k+1, l, (l+r)/2);
_add_val(x, a, b, 2*k+2, (l+r)/2, r);
update(k);
}
void _update_val(ll x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return;
}
if(a <= l && r <= b) {
updateall(k, x);
return;
}
push(k);
_update_val(x, a, b, 2*k+1, l, (l+r)/2);
_update_val(x, a, b, 2*k+2, (l+r)/2, r);
update(k);
}
ll _query_max(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return -inf;
}
if(a <= l && r <= b) {
return max_v[k];
}
push(k);
ll lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
ll rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
return max(lv, rv);
}
ll _query_min(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return inf;
}
if(a <= l && r <= b) {
return min_v[k];
}
push(k);
ll lv = _query_min(a, b, 2*k+1, l, (l+r)/2);
ll rv = _query_min(a, b, 2*k+2, (l+r)/2, r);
return min(lv, rv);
}
ll _query_sum(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return 0;
}
if(a <= l && r <= b) {
return sum[k];
}
push(k);
ll lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);
ll rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);
return lv + rv;
}
public:
SegmentTree(int n) {
SegmentTree(n, nullptr);
}
SegmentTree(int n, ll *a) : n(n) {
n0 = 1;
while(n0 < n) n0 <<= 1;
for(int i=0; i<2*n0; ++i) ladd[i] = 0, lval[i] = inf;
len[0] = n0;
for(int i=0; i<n0-1; ++i) len[2*i+1] = len[2*i+2] = (len[i] >> 1);
for(int i=0; i<n; ++i) {
max_v[n0-1+i] = min_v[n0-1+i] = sum[n0-1+i] = (a != nullptr ? a[i] : 0);
smax_v[n0-1+i] = -inf;
smin_v[n0-1+i] = inf;
max_c[n0-1+i] = min_c[n0-1+i] = 1;
}
for(int i=n; i<n0; ++i) {
max_v[n0-1+i] = smax_v[n0-1+i] = -inf;
min_v[n0-1+i] = smin_v[n0-1+i] = inf;
max_c[n0-1+i] = min_c[n0-1+i] = 0;
}
for(int i=n0-2; i>=0; i--) {
update(i);
}
}
// range minimize query
void update_min(int a, int b, ll x) {
_update_min(x, a, b, 0, 0, n0);
}
// range maximize query
void update_max(int a, int b, ll x) {
_update_max(x, a, b, 0, 0, n0);
}
// range add query
void add_val(int a, int b, ll x) {
_add_val(x, a, b, 0, 0, n0);
}
// range update query
void update_val(int a, int b, ll x) {
_update_val(x, a, b, 0, 0, n0);
}
// range minimum query
ll query_max(int a, int b) {
return _query_max(a, b, 0, 0, n0);
}
// range maximum query
ll query_min(int a, int b) {
return _query_min(a, b, 0, 0, n0);
}
// range sum query
ll query_sum(int a, int b) {
return _query_sum(a, b, 0, 0, n0);
}
};
ll a[N];
main(){
INT(n);
constexpr int T = 20000;
SegmentTree seg1(N,a),seg2(N,a);
ll pre = 0;
while(n--){
INT(a,b,c,d);
seg1.update_max(a+T,c+T,-b);
seg2.update_max(a+T,c+T,d);
ll sum = seg1.query_sum(0,N) + seg2.query_sum(0,N);
cout << sum - pre << endl;
pre = sum;
}
}