Submission #57111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
57111	2018-07-14T03:38:34 Z	Benq	Trading (IZhO13_trading)	C++14	0 / 100	525 ms	66560 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;
multiset<int> M;
vi ad[MX], del[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);
        del[b+1].pb(c-a);
    }
    FOR(i,1,n+1) {
        for (int j: ad[i]) M.insert(j);
        for (int j: del[i]) M.erase(M.find(j));
        if (sz(M)) cout << *M.rbegin()+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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	14584 KB	Output is correct
2	Correct	19 ms	14704 KB	Output is correct
3	Correct	20 ms	14800 KB	Output is correct
4	Correct	18 ms	14820 KB	Output is correct
5	Correct	16 ms	14940 KB	Output is correct
6	Correct	17 ms	15152 KB	Output is correct
7	Correct	240 ms	26272 KB	Output is correct
8	Correct	302 ms	30308 KB	Output is correct
9	Correct	352 ms	33536 KB	Output is correct
10	Correct	321 ms	37916 KB	Output is correct
11	Correct	349 ms	42152 KB	Output is correct
12	Correct	365 ms	47692 KB	Output is correct
13	Correct	333 ms	51056 KB	Output is correct
14	Correct	360 ms	56504 KB	Output is correct
15	Correct	427 ms	61588 KB	Output is correct
16	Runtime error	525 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
17	Halted	0 ms	0 KB	-