| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 396887 |
2021-04-30T22:40:27 Z |
duality |
Dungeon 3 (JOI21_ho_t5) |
C++11 |
|
4000 ms |
532620 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 disc[200000],fin[200000],num = 0;
vi adjList[200000];
int doDFS(int u) {
int i;
disc[u] = num++;
for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
fin[u] = num;
return 0;
}
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] != N) parent2[j][i] = parent2[parent2[j][i-1]][i-1];
else parent2[j][i] = N;
}
}
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 < N; i++) {
if (l[i] != -1) adjList[l[i]].pb(i);
}
for (i = 0; i < N; i++) {
if (l[i] == -1) doDFS(i);
}
events.clear();
for (i = 0; i < N; i++) {
if (l[i] >= 0) events.pb((event){i,i,B[i],pre[i]-pre[l[i]]});
}
sort(events.begin(),events.end(),comp);
for (i = 0; i < events.size(); i++) {
bit2[0].update(disc[events[i].l],events[i].w);
bit2[0].update(fin[events[i].l],-events[i].w);
}
j = 0;
for (i = 0; i < queries.size(); i++) {
while ((j < events.size()) && (events[j].x < queries[i].first)) {
bit2[0].update(disc[events[j].l],-events[j].w);
bit2[0].update(fin[events[j].l],events[j].w);
bit1[0].update(disc[events[j].l],events[j].x*events[j].w);
bit1[0].update(fin[events[j].l],-events[j].x*events[j].w);
j++;
}
bit1[0].query(disc[T[queries[i].second]],queries[i].second,1);
bit2[0].query(disc[T[queries[i].second]],queries[i].second,queries[i].first);
int u = T[queries[i].second];
for (k = logn-1; k >= 0; k--) {
if (parent[u][k] >= S[queries[i].second]) u = parent[u][k];
}
bit1[0].query(disc[u],queries[i].second,-1);
bit2[0].query(disc[u],queries[i].second,-queries[i].first);
}
bit1[0].process(),bit2[0].process();
for (i = 0; i < N; i++) adjList[i].clear();
num = 0;
for (i = 0; i < N; i++) {
if (r[i] != N) adjList[r[i]].pb(i);
}
for (i = 0; i < N; i++) {
if (r[i] == N) doDFS(i);
}
events.clear();
for (i = 0; i < N; i++) {
if (r[i] < N) events.pb((event){i,i,B[i],pre[r[i]]-pre[i]});
}
sort(events.begin(),events.end(),comp);
for (i = 0; i < events.size(); i++) {
bit2[0].update(disc[events[i].l],events[i].w);
bit2[0].update(fin[events[i].l],-events[i].w);
}
j = 0;
for (i = 0; i < queries.size(); i++) {
while ((j < events.size()) && (events[j].x < queries[i].first)) {
bit2[0].update(disc[events[j].l],-events[j].w);
bit2[0].update(fin[events[j].l],events[j].w);
bit1[0].update(disc[events[j].l],events[j].x*events[j].w);
bit1[0].update(fin[events[j].l],-events[j].x*events[j].w);
j++;
}
bit1[0].query(disc[S[queries[i].second]],queries[i].second,1);
bit2[0].query(disc[S[queries[i].second]],queries[i].second,queries[i].first);
int u = S[queries[i].second];
for (k = logn-1; k >= 0; k--) {
if (parent2[u][k] <= T[queries[i].second]) u = parent2[u][k];
}
bit1[0].query(disc[u],queries[i].second,-1);
bit2[0].query(disc[u],queries[i].second,-queries[i].first);
}
bit1[0].process(),bit2[0].process();
for (i = 0; i < M; i++) {
if (query(S[i],T[i]) > U[i]) 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]);
ans[i] += (b-min(a+b,(LLI) U[i]))*B[j];
}
j = parent[j][0];
}
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 doDFS(int)':
Main.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
| ~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:185:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:189: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]
189 | for (i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
Main.cpp:190:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | while ((j < events.size()) && (events[j].x < queries[i].first)) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:215:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:220: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]
220 | for (i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
Main.cpp:221:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | while ((j < events.size()) && (events[j].x < queries[i].first)) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:252:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
252 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:257: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]
257 | for (i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
Main.cpp:258:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
258 | while ((j < events.size()) && (events[j].x < queries[i].first)) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%d %d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:129:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
129 | for (i = 0; i < N; i++) scanf("%d",&A[i]),pre[i+1] = pre[i]+A[i];
| ~~~~~^~~~~~~~~~~~
Main.cpp:130:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | for (i = 0; i < N; i++) scanf("%d",&B[i]);
| ~~~~~^~~~~~~~~~~~
Main.cpp:131:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
131 | 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 |
35 ms |
20696 KB |
Output is correct |
| 2 |
Correct |
32 ms |
17728 KB |
Output is correct |
| 3 |
Correct |
21 ms |
17736 KB |
Output is correct |
| 4 |
Correct |
36 ms |
20724 KB |
Output is correct |
| 5 |
Correct |
33 ms |
17800 KB |
Output is correct |
| 6 |
Correct |
19 ms |
17744 KB |
Output is correct |
| 7 |
Correct |
31 ms |
20812 KB |
Output is correct |
| 8 |
Correct |
32 ms |
17756 KB |
Output is correct |
| 9 |
Correct |
18 ms |
17748 KB |
Output is correct |
| 10 |
Correct |
34 ms |
20720 KB |
Output is correct |
| 11 |
Correct |
32 ms |
17676 KB |
Output is correct |
| 12 |
Correct |
21 ms |
17652 KB |
Output is correct |
| 13 |
Correct |
33 ms |
21064 KB |
Output is correct |
| 14 |
Correct |
23 ms |
19020 KB |
Output is correct |
| 15 |
Correct |
24 ms |
19044 KB |
Output is correct |
| 16 |
Correct |
40 ms |
20712 KB |
Output is correct |
| 17 |
Correct |
31 ms |
20320 KB |
Output is correct |
| 18 |
Correct |
27 ms |
17312 KB |
Output is correct |
| 19 |
Correct |
17 ms |
17364 KB |
Output is correct |
| 20 |
Correct |
67 ms |
17952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
324 ms |
92080 KB |
Output is correct |
| 2 |
Correct |
551 ms |
135472 KB |
Output is correct |
| 3 |
Execution timed out |
4051 ms |
69416 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3075 ms |
532620 KB |
Output is correct |
| 2 |
Execution timed out |
4072 ms |
225964 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
20696 KB |
Output is correct |
| 2 |
Correct |
32 ms |
17728 KB |
Output is correct |
| 3 |
Correct |
21 ms |
17736 KB |
Output is correct |
| 4 |
Correct |
36 ms |
20724 KB |
Output is correct |
| 5 |
Correct |
33 ms |
17800 KB |
Output is correct |
| 6 |
Correct |
19 ms |
17744 KB |
Output is correct |
| 7 |
Correct |
31 ms |
20812 KB |
Output is correct |
| 8 |
Correct |
32 ms |
17756 KB |
Output is correct |
| 9 |
Correct |
18 ms |
17748 KB |
Output is correct |
| 10 |
Correct |
34 ms |
20720 KB |
Output is correct |
| 11 |
Correct |
32 ms |
17676 KB |
Output is correct |
| 12 |
Correct |
21 ms |
17652 KB |
Output is correct |
| 13 |
Correct |
33 ms |
21064 KB |
Output is correct |
| 14 |
Correct |
23 ms |
19020 KB |
Output is correct |
| 15 |
Correct |
24 ms |
19044 KB |
Output is correct |
| 16 |
Correct |
40 ms |
20712 KB |
Output is correct |
| 17 |
Correct |
31 ms |
20320 KB |
Output is correct |
| 18 |
Correct |
27 ms |
17312 KB |
Output is correct |
| 19 |
Correct |
17 ms |
17364 KB |
Output is correct |
| 20 |
Correct |
67 ms |
17952 KB |
Output is correct |
| 21 |
Correct |
324 ms |
92080 KB |
Output is correct |
| 22 |
Correct |
551 ms |
135472 KB |
Output is correct |
| 23 |
Execution timed out |
4051 ms |
69416 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
