Submission #57112

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
57112	2018-07-14T03:42:31 Z	Benq	Trading (IZhO13_trading)	C++14	100 / 100	298 ms	38520 KB

trading

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 300005;
 
int n,m;
priority_queue<pi> p;
vpi ad[MX];
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    F0R(i,m) {
        int a,b,c; cin >> a >> b >> c;
        ad[a].pb({c-a,b});
    }
    FOR(i,1,n+1) {
        for (auto j: ad[i]) p.push(j);
        while (sz(p) && p.top().s < i) p.pop();
        if (sz(p)) cout << p.top().f+i << " ";
        else cout << 0 << " ";
    }
}
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7444 KB	Output is correct
2	Correct	11 ms	7444 KB	Output is correct
3	Correct	13 ms	7588 KB	Output is correct
4	Correct	11 ms	7588 KB	Output is correct
5	Correct	10 ms	7704 KB	Output is correct
6	Correct	11 ms	7872 KB	Output is correct
7	Correct	171 ms	13220 KB	Output is correct
8	Correct	183 ms	14012 KB	Output is correct
9	Correct	176 ms	14316 KB	Output is correct
10	Correct	183 ms	14316 KB	Output is correct
11	Correct	188 ms	14544 KB	Output is correct
12	Correct	164 ms	15312 KB	Output is correct
13	Correct	180 ms	15312 KB	Output is correct
14	Correct	223 ms	15312 KB	Output is correct
15	Correct	292 ms	16240 KB	Output is correct
16	Correct	223 ms	16240 KB	Output is correct
17	Correct	296 ms	20356 KB	Output is correct
18	Correct	288 ms	26688 KB	Output is correct
19	Correct	298 ms	30960 KB	Output is correct
20	Correct	244 ms	38520 KB	Output is correct