Submission #498125

#TimeUsernameProblemLanguageResultExecution timeMemory
498125vinnipuh01Meteors (POI11_met)C++17
100 / 100
4793 ms65536 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> //#define int long long //#pragma GCC optimization("g", on) //#pragma GCC optimize ("inline") //#pragma GCC optimization("03") //#pragma GCC optimization("unroll-loops") //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") using namespace std; const long long oo = 1000000000000000000; long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen ( "sum.in", "r", stdin ) */ vector <int> vv[ 300002 ]; vector <int> v[ 300002 ]; int L[ 300002 ], R[ 300002 ]; int an[ 300002 ]; long long int t[ 1200002 ]; //void pus( int v ) { // if ( p[ v ] ) { // p[ v + v ] += p[ v ]; // p[ v + v + 1 ] += p[ v ]; // t[ v + v ] += p[ v ]; // t[ v + v + 1 ] += p[ v ]; // p[ v ] = 0; // } //} void gett( int v, int tl, int tr, int l, int r ) { if ( tl > r || tr < l ) return; if ( tl >= l && tr <= r ) { num += t[ v ]; return; } // pus( v ); int mid = ( tl + tr ) / 2; if ( mid >= l ) gett( v + v, tl, mid, l, r ); if ( mid + 1 <= r ) gett( v + v + 1, mid + 1, tr, l, r ); } void upd( int v, int tl, int tr, int pos ) { if ( tl > pos || tr < pos ) return; if ( tl == tr ) { t[ v ] += num; return; } // pus( v );. int mid = ( tl + tr ) / 2; if ( mid >= pos ) upd( v + v, tl, mid, pos ); if ( mid + 1 <= pos ) upd( v + v + 1, mid + 1, tr, pos ); t[ v ] = t[ v + v ] + t[ v + v + 1 ]; } main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; int a[ m + 1 ]; for ( int i = 1; i <= m; i ++ ) { cin >> a[ i ]; vv[ a[ i ] ].push_back( i ); } int b[ n + 1 ]; for ( int i = 1; i <= n; i ++ ) { cin >> b[ i ]; } int q; cin >> q; int l[ q + 1 ], r[ q + 1 ], x[ q + 1 ]; for ( int i = 1; i <= q; i ++ ) { cin >> l[ i ] >> r[ i ] >> x[ i ]; } for ( int i = 1; i <= n; i ++ ) L[ i ] = 1, R[ i ] = q + 1; ans = 1; int mid; while ( ans ) { ans = 0; memset( t, 0, sizeof( t ) ); // memset( p, 0, sizeof( p ) ); for ( int i = 1; i <= n; i ++ ) { // cout << i << " - " << L[ i ] << " " << R[ i ] << "\n"; if ( L[ i ] == R[ i ] ) continue; mid = ( L[ i ] + R[ i ] ) / 2; v[ mid ].push_back( i ); ans = 1; } for ( int j = 1; j <= q; j ++ ) { num = x[ j ]; if ( l[ j ] <= r[ j ] ) { upd( 1, 1, m, l[ j ] ); num = -x[ j ]; upd( 1, 1, m, r[ j ] + 1 ); } else { upd( 1, 1, m, 1 ); upd( 1, 1, m, l[ j ] ); num = -x[ j ]; upd( 1, 1, m, r[ j ] + 1 ); } if ( v[ j ].size() == 0 ) continue; for ( auto i : v[ j ] ) { num = 0; for ( auto pos : vv[ i ] ) { gett( 1, 1, m, 1, pos ); if ( num >= b[ i ] ) { break; } } // cout << i << " - " << num << "\n"; if ( num >= b[ i ] ) R[ i ] = j; else L[ i ] = j + 1; } v[ j ].clear(); } // for ( int j = 1; j <= q; j ++ ) { // num = -x[ j ]; // if ( l[ j ] <= r[ j ] ) // upd( 1, 1, m, l[ j ], r[ j ] ); // else // upd( 1, 1, m, 1, r[ j ] ), upd( 1, 1, m, l[ j ], m ); // } } for ( int i = 1; i <= n; i ++ ) { if ( L[ i ] <= q ) cout << L[ i ] << "\n"; else cout << "NIE\n"; } }

Compilation message (stderr)

met.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main () {
      | ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...