Submission #1123559

#TimeUsernameProblemLanguageResultExecution timeMemory
1123559LucaIlieFire (JOI20_ho_t5)C++20
0 / 100
406 ms38772 KiB
#include <bits/stdc++.h> using namespace std; struct query { int t, l, r; long long ans; }; const int MAX_N = 2e5; const int MAX_Q = 2e5; int a[MAX_N + 1], leftt[MAX_N + 1], rightt[MAX_N + 1], timeIncrease[MAX_N + 1]; vector<int> queriesByTime[MAX_N + 1]; vector<int> increasingSegmentsByTime[MAX_N + 1], constantSegmentsByTime[MAX_N + 1]; query queries[MAX_Q]; void computeSegmentEvents( int n, int sign ) { set<int> increasingSegments, constantSegments; for ( int t = 0; t <= n; t++ ) { for ( int i: increasingSegmentsByTime[t] ) { if ( increasingSegments.find( i ) == increasingSegments.end() ) increasingSegments.insert( i ); else increasingSegments.erase( i ); } for ( int i: constantSegmentsByTime[t] ) { if ( constantSegments.find( i ) == constantSegments.end() ) constantSegments.insert( i ); else constantSegments.erase( i ); } for ( int i: queriesByTime[t] ) { //printf( "QUERY %d\n", i ); for ( int j: increasingSegments ) queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] ); for ( int j: constantSegments ) queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 ); //printf( "\n\n\n" ); } } } int main() { int n, q; cin >> n >> q; for ( int i = 1; i <= n; i++ ) cin >> a[i]; for ( int i = 0; i < q; i++ ) { cin >> queries[i].t >> queries[i].l >> queries[i].r; queriesByTime[queries[i].t].push_back( i ); } vector<int> stack; for ( int i = 1; i <= n; i++ ) { while ( !stack.empty() && a[i] > a[stack.back()] ) stack.pop_back(); if ( !stack.empty() ) leftt[i] = stack.back(); else leftt[i] = -(n + 1); stack.push_back( i ); } while ( !stack.empty() ) stack.pop_back(); for ( int i = n; i >= 1; i-- ) { while ( !stack.empty() && a[i] > a[stack.back()] ) stack.pop_back(); if ( !stack.empty() ) rightt[i] = stack.back(); else rightt[i] = (n + 1); stack.push_back( i ); } for ( int t = 0; t <= n; t++ ) { increasingSegmentsByTime[t].clear(); constantSegmentsByTime[t].clear(); } for ( int i = 1; i <= n; i++ ) { // update + on trapezoid int goDown = i - leftt[i], goIncreasing = rightt[i] - i; timeIncrease[i] = 0; increasingSegmentsByTime[0].push_back( i ); increasingSegmentsByTime[goIncreasing].push_back( i ); constantSegmentsByTime[goIncreasing].push_back( i ); constantSegmentsByTime[goIncreasing + goDown - 1].push_back( i ); } computeSegmentEvents( n, 1 ); for ( int t = 0; t <= n; t++ ) { increasingSegmentsByTime[t].clear(); constantSegmentsByTime[t].clear(); } for ( int i = 1; i <= n; i++ ) { // update - on triangle int goDown = i - leftt[i], goIncreasing = rightt[i] - i; timeIncrease[i] = goDown; increasingSegmentsByTime[goDown].push_back( i ); increasingSegmentsByTime[goDown + goIncreasing - 1].push_back( i ); } computeSegmentEvents( n, -1 ); for ( int i = 0; i < q; i++ ) cout << queries[i].ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...