Submission #1003014

#TimeUsernameProblemLanguageResultExecution timeMemory
1003014hyakupAutobahn (COI21_autobahn)C++17
50 / 100
136 ms15800 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long struct evento{ int x, type, id; evento( int x = 0, int type = 0, int id = 0 ) : x(x), type(type), id(id) {} bool operator < ( evento e ){ if( x == e.x ) type < e.type; return x < e.x; } }; vector<evento> line; const int maxn = 1e5 + 10; vector<int> resp( 2*maxn, -1 ); int main(){ int n, k, x; cin >> n >> k >> x; for( int i = 1; i <= n; i++ ){ int l, t, r; cin >> l >> t >> r; line.push_back( evento( l - 1, 1, 0 ) ); line.push_back( evento( l + t - 1, 2, 0 ) ); line.push_back( evento( r - x, 3, 2*i ) ); line.push_back( evento( r, 3, 2*i ) ); line.push_back( evento( l + t - 1, 3, 2*i + 1 ) ); line.push_back( evento( l + t + x - 1, 3, 2*i + 1 ) ); line.push_back( evento( r, 4, 0 ) ); } sort( line.begin(), line.end() ); ll ativos = 0, criticos = 0; ll sum = 0; ll ans = 0; for(int i = 0; i < line.size(); i++ ){ if( i > 0 && ativos >= k ) sum += criticos*(line[i].x - line[i - 1].x ); auto cur = line[i]; if( cur.type == 1 ) ativos++; if( cur.type == 2 ) criticos++; if( cur.type == 3 ){ if( resp[cur.id] == -1 ) resp[cur.id] = sum; else ans = max( ans, sum - resp[cur.id] ); } if( cur.type == 4 ){ ativos--; criticos--; } } cout << ans << endl; }

Compilation message (stderr)

autobahn.cpp: In member function 'bool evento::operator<(evento)':
autobahn.cpp:9:25: warning: statement has no effect [-Wunused-value]
    9 |     if( x == e.x ) type < e.type;
      |                    ~~~~~^~~~~~~~
autobahn.cpp: In function 'int main()':
autobahn.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<evento>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i = 0; i < line.size(); i++ ){
      |                  ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...