Submission #885752

#	Time	Username	Problem	Language	Result	Execution time	Memory
885752		qin	Fire (JOI20_ho_t5)	C++17	14 / 100	257 ms	54408 KiB

ho_t5

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int base = 1;
struct seg{
		struct Node{
				ll a, b; int la, lb;
				Node(): a(0), b(0), la(0), lb(0) {}
				Node(ll aa, ll bb, int laa, int lbb) : a(aa), b(bb), la(laa), lb(lbb) {}
		};
		vector<Node> t;
		vector<ll> tab;
		void merge(int &i){
				t[i].a = t[i<<1].a + t[i<<1|1].a, t[i].b = t[i<<1].b + t[i<<1|1].b;
				t[i].la = t[i<<1].la + t[i<<1|1].la, t[i].lb = t[i<<1].lb + t[i<<1|1].lb;
		}
		void init(int n, vector<ll> &a){
				while(base < n) base <<= 1;
				t.resize(base<<1); tab = a;
				for(int i = 1; i <= n; ++i) t[i+base-1] = Node(a[i], a[i], 1, 1);
				for(int i = base-1; i; --i) merge(i);
		}
		void update_point(int i, ll a, ll b, int la, int lb){ for(i += base-1, t[i] = Node(a, b, la, lb), i >>= 1; i; i >>= 1) merge(i); }
		ll first_k(int i, int s, int e, int &x, int &y, int &k, int &T){
				if(!k) return 0;
				int mid = (s+e)>>1;
				if(x <= s && e <= y){
						int sum = t[i].la*T + t[i].lb;
						if(sum <= k){ k -= sum; return t[i].a*T + t[i].b; }
						else{
								if(s != e) return first_k(i<<1, s, mid, x, y, k, T) + first_k(i<<1|1, mid+1, e, x, y, k, T);
								else{ ll ret = tab[s]*k; k = 0; return ret; }
						}
				} ll ret = 0;
				if(x <= mid) ret += first_k(i<<1, s, mid, x, y, k, T);
				if(mid < y) ret += first_k(i<<1|1, mid+1, e, x, y, k, T);
				return ret;
		}
		ll query_interval(int i, int s, int e, int &x, int &y, int &T){
				if(x <= s && e <= y){
						//printf("%d %d\n", t[i].a, t[i].b);
						return t[i].a*T + t[i].b;
				}
				int mid = (s+e)>>1; ll ret = 0;
				if(x <= mid) ret += query_interval(i<<1, s, mid, x, y, T);
				if(mid < y) ret += query_interval(i<<1|1, mid+1, e, x, y, T);
				return ret;
		}
		ll query(int x, int y, int T){
				if(x > y) return 0;
				return query_interval(1, 1, base, x, y, T);
		}
		ll firstk(int x, int y, int k, int T){
				if(x > y) return 0;
				return first_k(1, 1, base, x, y, k, T);
		}
};
struct ev{
		int t, i;
		ev(){}
		ev(int tt, int ii) : t(tt), i(ii) {}
		bool operator <(const ev &x) const{ return t < x.t; }
};
struct qr{
		int a, b, i;
		qr(){}
		qr(int aa, int bb, int ii) : a(aa), b(bb), i(ii) {}
};
void answer(){
		int n, q; scanf("%d%d", &n, &q);
		vector<ll> t(n+1);
		vector<int> nxt(n+1), bef(n+1);
		for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
		seg seg; seg.init(n, t);
		
		vector<int> st;
		for(int i = 1; i <= n; ++i){
				while(!st.empty() && t[st.back()] < t[i]) st.pop_back();
				if(st.empty()) bef[i] = n+1;
				else bef[i] = i-st.back();
				st.emplace_back(i);
		} st = vector<int>();
		for(int i = n; i; --i){
				while(!st.empty() && t[st.back()] < t[i]) st.pop_back();
				if(st.empty()) nxt[i] = n+1-i;
				else nxt[i] = st.back()-i;
				st.emplace_back(i);
		} st = vector<int>();
		
		vector<vector<ev>> event(n+2);
		set<int> active;
		for(int i = 1; i <= n; ++i) event[min(n+1, min(bef[i], nxt[i]))].emplace_back(0, i), event[min(n+1, max(bef[i], nxt[i]))].emplace_back(1, i),
									event[min(n+1, min(bef[i], nxt[i])+max(bef[i], nxt[i]))].emplace_back(2, i), active.emplace(i);
		//for(int i = 1; i <= n; ++i) printf("%d %d\n", bef[i], nxt[i]);
		vector<vector<qr>> queries(n+1);
		for(int i = 1; i <= q; ++i){ int a, b, T; scanf("%d%d%d", &T, &a, &b), queries[T].emplace_back(a, b, i);}
		vector<ll> result(q+1);
		
		for(int T = 1; T <= n; ++T){
				for(ev &u : event[T]){
						//printf("%d, %d: %d\n", T, u.i, u.t);
						if(!u.t){
								if(u.i != 1) active.erase(u.i);
								//printf("%d %d\n", T, u.i);
								seg.update_point(u.i, 0, t[u.i]*T, 0, T);
						} else if(u.t == 1) seg.update_point(u.i, -t[u.i], t[u.i]*(min(bef[u.i], nxt[u.i])+T-1), -1, min(bef[u.i], nxt[u.i])+T-1);
						else seg.update_point(u.i, 0, 0, 0, 0);
				}
				for(qr &u : queries[T]){
						auto it1 = active.upper_bound(u.a); it1 = prev(it1);
						auto it2 = active.upper_bound(u.b); it2 = prev(it2);
						result[u.i] = seg.query(*it1, (*it2)-1, T)-seg.firstk(*it1, u.a-1, u.a-(*it1), T)+seg.firstk(*it2, u.b, u.b-(*it2)+1, T);
						//printf("%d: %d %d: %lld %lld %lld\n", u.i, *it1, *it2, seg.query(*it1, (*it2)-1, T), seg.firstk(*it1, u.a-1, u.a-(*it1), T), seg.firstk(*it2, u.b, u.b-(*it2)+1, T));
						//printf("%d %d %d, %lld\n", *it2, u.b, u.b-(*it2)+1, seg.firstk(*it2, u.b, u.b-(*it2)+1, T));
				}
				//if(T == 3) printf("%lld\n", seg.query(4, 4, T));
		}
		for(int i = 1; i <= q; ++i) printf("%lld\n", result[i]);
}
int main(){
		int T = 1; //scanf("%d", &T);
		//ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'void answer()':
ho_t5.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   int n, q; scanf("%d%d", &n, &q);
      |             ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:99:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:122:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |   for(int i = 1; i <= q; ++i){ int a, b, T; scanf("%d%d%d", &T, &a, &b), queries[T].emplace_back(a, b, i);}
      |                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80