oj.uz

Submission #13115

# Submission time Handle Problem Language Result Execution time Memory
13115 2015-01-31T09:18:39 Z dohyun0324 Trading (IZhO13_trading) C++
100 / 100
 629 ms 24088 KB 
#include<stdio.h>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
set<int>q;
map<int,int>ch;
int n,m;
struct data{
    int l,r,x;
    bool operator<(const data&r)const{
        return l<r.l;
    }
}a[300010];
struct data2{
    int l,r,x;
    bool operator<(const data2&p)const{
        return r<p.r;
    }
}b[300010];
int main()
{
    int i,j,p1=1,p2=1;
    set<int>::iterator p;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].x);
        b[i].l=a[i].l; b[i].r=a[i].r; b[i].x=a[i].x;
    }
    sort(a+1,a+m+1);
    sort(b+1,b+m+1);
    for(i=1;i<=n;i++){
        for(j=p1;j<=m;j++){
            if(a[j].l>i) break;
            ch[a[j].x-a[j].l]++;
            q.insert(a[j].x-a[j].l);
        }
        p1=j;
        for(j=p2;j<=m;j++){
            if(b[j].r>=i) break;
            ch[b[j].x-b[j].l]--;
            if(ch[b[j].x-b[j].l]==0) q.erase(b[j].x-b[j].l);
        }
        p2=j;
        if(q.empty()){printf("0 "); continue;}
        p=q.end(); p--;
        printf("%d ",(*p)+i);
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8248 KB Output is correct
2 Correct 0 ms 8248 KB Output is correct
3 Correct 0 ms 8248 KB Output is correct
4 Correct 0 ms 8248 KB Output is correct
5 Correct 0 ms 8248 KB Output is correct
6 Correct 4 ms 8380 KB Output is correct
7 Correct 301 ms 15376 KB Output is correct
8 Correct 321 ms 16564 KB Output is correct
9 Correct 358 ms 17356 KB Output is correct
10 Correct 407 ms 20524 KB Output is correct
11 Correct 405 ms 18412 KB Output is correct
12 Correct 479 ms 21844 KB Output is correct
13 Correct 417 ms 19204 KB Output is correct
14 Correct 497 ms 22504 KB Output is correct
15 Correct 550 ms 21712 KB Output is correct
16 Correct 542 ms 20524 KB Output is correct
17 Correct 515 ms 22372 KB Output is correct
18 Correct 600 ms 22504 KB Output is correct
19 Correct 573 ms 24088 KB Output is correct
20 Correct 629 ms 23428 KB Output is correct