oj.uz

Submission #13129

# Submission time Handle Problem Language Result Execution time Memory
13129 2015-01-31T15:04:43 Z gs14004 Trading (IZhO13_trading) C++14
100 / 100
 313 ms 12236 KB 
#include <cstdio>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
typedef pair<int,int> pi;

multiset<int> s;

pi ins[300005], del[300005];
int n,m;

int main(){
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        int s,e,x;
        scanf("%d %d %d",&s,&e,&x);
        ins[i] = pi(s,x-s);
        del[i] = pi(e,x-s);
    }
    sort(ins,ins+m);
    sort(del,del+m);
    int p1 = 0, p2 = 0;
    for (int i=1; i<=n; i++) {
        int mv = p1;
        while (mv < m && ins[mv].first == i) {
            mv++;
        }
        for (int j=p1; j<mv; j++) {
            s.insert(ins[j].second);
        }
        p1 = mv;
        auto x = s.end();
        if(x == s.begin()) printf("0 ");
        else printf("%d ",*(--x) + i);
        mv = p2;
        while (mv < m && del[mv].first == i) {
            mv++;
        }
        for (int j=p2; j<mv; j++) {
            s.erase(s.find(del[j].second));
        }
        p2 = mv;
    }
    
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5900 KB Output is correct
2 Correct 0 ms 5900 KB Output is correct
3 Correct 0 ms 5900 KB Output is correct
4 Correct 0 ms 5900 KB Output is correct
5 Correct 0 ms 5900 KB Output is correct
6 Correct 0 ms 5900 KB Output is correct
7 Correct 156 ms 8276 KB Output is correct
8 Correct 161 ms 8012 KB Output is correct
9 Correct 161 ms 9068 KB Output is correct
10 Correct 215 ms 10784 KB Output is correct
11 Correct 200 ms 8012 KB Output is correct
12 Correct 231 ms 11180 KB Output is correct
13 Correct 219 ms 8672 KB Output is correct
14 Correct 223 ms 10388 KB Output is correct
15 Correct 251 ms 9992 KB Output is correct
16 Correct 253 ms 8936 KB Output is correct
17 Correct 256 ms 10124 KB Output is correct
18 Correct 308 ms 12236 KB Output is correct
19 Correct 196 ms 9992 KB Output is correct
20 Correct 313 ms 9860 KB Output is correct