CSES - HIIT Open 2019 - Results
Submission details
Task:Final Array
Sender:Barely div 1
Submission time:2019-05-25 12:37:56 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.17 sdetails
#2ACCEPTED0.14 sdetails
#3ACCEPTED0.03 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:45:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto i : A) cout << i << " "; cout << endl;
   ^~~
input/code.cpp:45:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto i : A) cout << i << " "; cout << endl;
                                     ^~~~

Code

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long LL;

#define Foxnews cin
#define Tweet cout

int main() {
  priority_queue<pair<int,int>> pq;
  vector<tuple<int,int,int>> ops;
  int n, m, a, b, x;

  Foxnews >> n >> m;

  vector<int> A(n);

  for(int i=0; i<m; i++) {
    Foxnews >> a >> b >> x;

    ops.emplace_back(a,b,x);
  }

  sort(ops.rbegin(), ops.rend());

  for(int i=1; i<=n; i++) {
    //cout << "i is " << i << endl;
    //for(auto t : ops) {
    //  cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
    //}
    while(get<0>(ops.back()) == i) {
      tie(a, b, x) = ops.back();
      ops.pop_back();
      pq.push({x-a, b});
    }
    while(!pq.empty() && pq.top().second < i)
      pq.pop(); // remove expired
    //cout << pq.size() << " items in queue, top " << pq.top().first << "/" << pq.top().second << endl;
    if(!pq.empty()) A[i-1] = pq.top().first + i;
  }
  for(auto i : A) cout << i << " "; cout << endl;
  //for(auto t : ops) {
  //  cout << "At 0 is " << x-a << endl;
  //}
}

Test details

Test 1

Verdict: ACCEPTED

input
100000 100000
29706 39977 913671103
20575 89990 878449866
1691 70785 229168045
81099 81323 611730238
...

correct output
227121122 450258482 450258483 ...

user output
227121122 450258482 450258483 ...

Test 2

Verdict: ACCEPTED

input
100000 100000
1 100000 1
1 100000 2
1 100000 3
1 100000 4
...

correct output
100000 100001 100002 100003 10...

user output
100000 100001 100002 100003 10...

Test 3

Verdict: ACCEPTED

input
8 2
1 4 1
1 8 1

correct output
1 2 3 4 5 6 7 8

user output
1 2 3 4 5 6 7 8