oj.uz

Submission #947917

# Submission time Handle Problem Language Result Execution time Memory
947917 2024-03-17T09:10:10 Z vjudge306 Trading (IZhO13_trading) C++14
100 / 100
 204 ms 32068 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
 pair<int,int>nm[300005]; int X;
struct in {
int x; int i; int v;
};
struct com {

bool operator()(const pair<int,int>&a, const pair<int,int>&b) const {

//int i=, j=;

//if (i>j)
    return (a.A+(X-nm[a.B].A))<(b.A+(X-nm[b.B].A));
//return b.A<(a.A*-1);
}
};
signed main() {

    x_x
int n=0,m=0; cin>>n>>m; vector<in>ar[n];
for (int i=0, a, b, c; i<m; i++)
cin>>a>>b>>c, ar[a-1].emp({1,i,c}), nm[i]={a-1,b-1};

priority_queue<pair<int,int>,vector<pair<int,int>>,com>pq;

for(int i=0; i<n; i++) {
    int mx=0; X=i;

    while (!pq.empty()) {
    pair<int,int>y=pq.top();
    if (nm[y.B].B<i)
        {pq.pop(); continue;}
     mx=y.A+(i-nm[y.B].A);
     break;
     }
    if(!ar[i].empty()) {
     for (auto j:ar[i]) {
        if (j.x) {
            mx=max(mx, j.v);
    pq.push({j.v, j.i});
        }
    }
    }
  cout<<mx<<' ';
}
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 92 ms 16480 KB Output is correct
8 Correct 87 ms 17968 KB Output is correct
9 Correct 94 ms 19200 KB Output is correct
10 Correct 112 ms 22680 KB Output is correct
11 Correct 117 ms 20904 KB Output is correct
12 Correct 124 ms 24496 KB Output is correct
13 Correct 131 ms 23032 KB Output is correct
14 Correct 133 ms 23536 KB Output is correct
15 Correct 155 ms 27584 KB Output is correct
16 Correct 174 ms 26536 KB Output is correct
17 Correct 152 ms 27664 KB Output is correct
18 Correct 204 ms 29604 KB Output is correct
19 Correct 171 ms 29876 KB Output is correct
20 Correct 191 ms 32068 KB Output is correct