| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 396877 |
2021-04-30T21:46:37 Z |
duality |
Dungeon 3 (JOI21_ho_t5) |
C++11 |
|
4000 ms |
471568 KB |
#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
int N;
int A[200000],B[200000],S[200000],T[200000],U[200000];
LLI pre[200001];
int l[200000],r[200000];
vi s;
int sparse[200000][18],logg[200001];
pii sparse2[200000][18];
int query(int s,int e) {
int l = logg[e-s+1];
return max(sparse[s][l],sparse[e-(1 << l)+1][l]);
}
int query2(int s,int e) {
int l = logg[e-s+1];
return min(sparse2[s][l],sparse2[e-(1 << l)+1][l]).second;
}
LLI ans[200000];
vpii queries;
struct event {
int l,r,w;
LLI x;
};
vector<event> events;
bool comp(event a,event b) {
return a.x < b.x;
}
LLI bit[200001];
struct data {
vector<pair<pii,LLI> > vv;
int update(int i,LLI num) {
vv.pb(mp(mp(i,-1),num));
return 0;
}
int query(int i,int a,LLI w) {
vv.pb(mp(mp(i,a),w));
return 0;
}
int process() {
int i,j;
for (i = 0; i < vv.size(); i++) {
if (vv[i].first.second == -1) {
for (j = vv[i].first.first+1; j <= N; j += j & (-j)) bit[j] += vv[i].second;
}
else {
for (j = vv[i].first.first+1; j > 0; j -= j & (-j)) ans[vv[i].first.second] += vv[i].second*bit[j];
}
}
for (i = 0; i < vv.size(); i++) {
if (vv[i].first.second == -1) {
for (j = vv[i].first.first+1; j <= N; j += j & (-j)) bit[j] = 0;
}
}
vv.clear();
return 0;
}
};
data bit1[200001],bit2[200001];
int parent[200000][18],depth[200000],logn;
int parent2[200000][18],depth2[200000];
int main() {
int i;
int M;
scanf("%d %d",&N,&M);
for (i = 0; i < N; i++) scanf("%d",&A[i]),pre[i+1] = pre[i]+A[i];
for (i = 0; i < N; i++) scanf("%d",&B[i]);
for (i = 0; i < M; i++) scanf("%d %d %d",&S[i],&T[i],&U[i]),S[i]--,T[i] -= 2;
int j;
for (i = 0; i < N; i++) {
while (!s.empty() && (B[s.back()] > B[i])) s.pop_back();
if (s.empty()) l[i] = -1;
else l[i] = s.back();
s.pb(i);
}
s.clear();
for (i = N-1; i >= 0; i--) {
while (!s.empty() && (B[s.back()] >= B[i])) s.pop_back();
if (s.empty()) r[i] = N;
else r[i] = s.back();
s.pb(i);
}
for (i = 0; i < N; i++) sparse[i][0] = A[i],sparse2[i][0] = mp(B[i],i);
for (i = 1; (1 << i) <= N; i++) {
for (j = 0; j <= N-(1 << i); j++) {
sparse[j][i] = max(sparse[j][i-1],sparse[j+(1 << (i-1))][i-1]);
sparse2[j][i] = min(sparse2[j][i-1],sparse2[j+(1 << (i-1))][i-1]);
}
}
for (i = 2; i <= N; i++) logg[i] = logg[i/2]+1;
for (i = 0; i < N; i++) parent[i][0] = l[i],depth[i] = ((l[i] == -1) ? 0:depth[l[i]]+1);
for (i = 1; (1 << i) < N; i++) {
for (j = 0; j < N; j++) {
if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
else parent[j][i] = -1;
}
}
for (i = N-1; i >= 0; i--) parent2[i][0] = r[i],depth2[i] = ((r[i] == N) ? 0:depth2[r[i]]+1);
for (i = 1; (1 << i) < N; i++) {
for (j = 0; j < N; j++) {
if (parent2[j][i-1] != -1) parent2[j][i] = parent2[parent2[j][i-1]][i-1];
else parent2[j][i] = -1;
}
}
logn = i;
int k;
for (i = 0; i < M; i++) {
if (query(S[i],T[i]) > U[i]) ans[i] = -1;
else queries.pb(mp(U[i],i));
}
sort(queries.begin(),queries.end());
for (i = 0; i < N; i++) {
if ((l[i] >= 0) && (r[i] < N)) {
events.pb((event){l[i],r[i],-B[i],pre[r[i]]-pre[l[i]]});
events.pb((event){l[i],r[i],B[i],pre[r[i]]-pre[i]});
events.pb((event){l[i],r[i],B[i],pre[i]-pre[l[i]]});
}
}
sort(events.begin(),events.end(),comp);
for (i = 0; i < events.size(); i++) {
for (k = events[i].l+1; k > 0; k -= k & (-k)) bit2[k].update(events[i].r,events[i].w);
}
j = 0;
for (i = 0; i < queries.size(); i++) {
while ((j < events.size()) && (events[j].x < queries[i].first)) {
for (k = events[j].l+1; k > 0; k -= k & (-k)) {
bit2[k].update(events[j].r,-events[j].w);
bit1[k].update(events[j].r,events[j].x*events[j].w);
}
j++;
}
for (k = S[queries[i].second]+1; k <= N; k += k & (-k)) {
bit1[k].query(T[queries[i].second],queries[i].second,1);
bit2[k].query(T[queries[i].second],queries[i].second,queries[i].first);
}
}
for (i = 0; i <= N; i++) bit1[i].process(),bit2[i].process();
for (i = 0; i < M; i++) {
if (ans[i] == -1) printf("-1\n");
else {
j = T[i];
while (j >= S[i]) {
if (l[j] >= S[i]) {
LLI a = min(pre[j]-pre[l[j]],(LLI) U[i]);
LLI b = min(pre[T[i]+1]-pre[j],(LLI) U[i]);
if (j != query2(S[i],T[i])) ans[i] += (a+b-min(a+b,(LLI) U[i]))*B[j];
}
j = parent[j][0];
}
j = S[i];
while (j <= T[i]) {
if (r[j] <= T[i]) {
LLI b = min(pre[r[j]]-pre[j],(LLI) U[i]);
if (j != query2(S[i],T[i])) ans[i] += b*B[j];
}
j = parent2[j][0];
}
/*for (j = S[i]; j <= T[i]; j++) {
if ((l[j] >= S[i]) && (r[j] <= T[i])) {
LLI a = min(pre[j]-pre[l[j]],(LLI) U[i]);
LLI b = min(pre[r[j]]-pre[j],(LLI) U[i]);
ans[i] += (a+b-min(a+b,(LLI) U[i]))*B[j];
}
else if (l[j] >= S[i]) {
LLI a = min(pre[j]-pre[l[j]],(LLI) U[i]);
LLI b = min(pre[T[i]+1]-pre[j],(LLI) U[i]);
ans[i] += (a+b-min(a+b,(LLI) U[i]))*B[j];
}
else if (r[j] <= T[i]) {
LLI b = min(pre[r[j]]-pre[j],(LLI) U[i]);
ans[i] += b*B[j];
}
}*/
j = query2(S[i],T[i]);
LLI b = min(pre[T[i]+1]-pre[j],(LLI) U[i]);
ans[i] += b*B[j];
printf("%lld\n",ans[i]);
}
}
return 0;
}
Compilation message
Main.cpp: In member function 'int data::process()':
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (i = 0; i < vv.size(); i++) {
| ~~^~~~~~~~~~~
Main.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (i = 0; i < vv.size(); i++) {
| ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:180:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for (i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
Main.cpp:181:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | while ((j < events.size()) && (events[j].x < queries[i].first)) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%d %d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:120:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | for (i = 0; i < N; i++) scanf("%d",&A[i]),pre[i+1] = pre[i]+A[i];
| ~~~~~^~~~~~~~~~~~
Main.cpp:121:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | for (i = 0; i < N; i++) scanf("%d",&B[i]);
| ~~~~~^~~~~~~~~~~~
Main.cpp:122:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | for (i = 0; i < M; i++) scanf("%d %d %d",&S[i],&T[i],&U[i]),S[i]--,T[i] -= 2;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
15116 KB |
Output is correct |
| 2 |
Correct |
29 ms |
11852 KB |
Output is correct |
| 3 |
Correct |
24 ms |
11892 KB |
Output is correct |
| 4 |
Correct |
24 ms |
15176 KB |
Output is correct |
| 5 |
Correct |
29 ms |
11924 KB |
Output is correct |
| 6 |
Correct |
25 ms |
11856 KB |
Output is correct |
| 7 |
Correct |
25 ms |
15244 KB |
Output is correct |
| 8 |
Correct |
30 ms |
11960 KB |
Output is correct |
| 9 |
Correct |
25 ms |
11928 KB |
Output is correct |
| 10 |
Correct |
24 ms |
15144 KB |
Output is correct |
| 11 |
Correct |
28 ms |
11880 KB |
Output is correct |
| 12 |
Correct |
24 ms |
11880 KB |
Output is correct |
| 13 |
Correct |
26 ms |
15428 KB |
Output is correct |
| 14 |
Correct |
34 ms |
13344 KB |
Output is correct |
| 15 |
Correct |
29 ms |
13440 KB |
Output is correct |
| 16 |
Correct |
39 ms |
15004 KB |
Output is correct |
| 17 |
Correct |
24 ms |
14868 KB |
Output is correct |
| 18 |
Correct |
22 ms |
11680 KB |
Output is correct |
| 19 |
Correct |
21 ms |
11684 KB |
Output is correct |
| 20 |
Correct |
55 ms |
12228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3246 ms |
71304 KB |
Output is correct |
| 2 |
Correct |
468 ms |
116848 KB |
Output is correct |
| 3 |
Execution timed out |
4089 ms |
49916 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2652 ms |
471568 KB |
Output is correct |
| 2 |
Execution timed out |
4065 ms |
166044 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
15116 KB |
Output is correct |
| 2 |
Correct |
29 ms |
11852 KB |
Output is correct |
| 3 |
Correct |
24 ms |
11892 KB |
Output is correct |
| 4 |
Correct |
24 ms |
15176 KB |
Output is correct |
| 5 |
Correct |
29 ms |
11924 KB |
Output is correct |
| 6 |
Correct |
25 ms |
11856 KB |
Output is correct |
| 7 |
Correct |
25 ms |
15244 KB |
Output is correct |
| 8 |
Correct |
30 ms |
11960 KB |
Output is correct |
| 9 |
Correct |
25 ms |
11928 KB |
Output is correct |
| 10 |
Correct |
24 ms |
15144 KB |
Output is correct |
| 11 |
Correct |
28 ms |
11880 KB |
Output is correct |
| 12 |
Correct |
24 ms |
11880 KB |
Output is correct |
| 13 |
Correct |
26 ms |
15428 KB |
Output is correct |
| 14 |
Correct |
34 ms |
13344 KB |
Output is correct |
| 15 |
Correct |
29 ms |
13440 KB |
Output is correct |
| 16 |
Correct |
39 ms |
15004 KB |
Output is correct |
| 17 |
Correct |
24 ms |
14868 KB |
Output is correct |
| 18 |
Correct |
22 ms |
11680 KB |
Output is correct |
| 19 |
Correct |
21 ms |
11684 KB |
Output is correct |
| 20 |
Correct |
55 ms |
12228 KB |
Output is correct |
| 21 |
Correct |
3246 ms |
71304 KB |
Output is correct |
| 22 |
Correct |
468 ms |
116848 KB |
Output is correct |
| 23 |
Execution timed out |
4089 ms |
49916 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
