oj.uz

Submission #41121

# Submission time Handle Problem Language Result Execution time Memory
41121 2018-02-13T02:43:04 Z 14kg trapezoid (balkan11_trapezoid) C++11
100 / 100
 395 ms 45840 KB 
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#define N 100001
#define MOD 30013

using namespace std;
struct REC{
    int dl, dr, ul, ur;
} in[N];
int n, M_len, nn;
pair<int,int> d[N], tree[N*8], out;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
set<int> S;
map<int,int> M;

bool cmp(REC x, REC y){
    if(x.dl!=y.dl) return x.dl<y.dl;
    return x.dr<y.dr;
}
pair<int,int> add(pair<int,int> tl, pair<int,int> tr){
    if(tl.first>tr.first) return tl;
    if(tl.first<tr.first) return tr;
    return {tl.first,(tl.second+tr.second)%MOD};
}
void update(int lev){
    tree[lev]=add(tree[lev*2],tree[lev*2+1]);
    if(lev>1) update(lev/2);
}
pair<int,int> get(int lev, int l, int r, int x, int y){
    if(r<x || y<l) return {0,0};
    if(x<=l && r<=y) return tree[lev];

    int mid=(l+r)/2;
    return add(get(lev*2,l,mid,x,y),get(lev*2+1,mid+1,r,x,y));
}
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d%d%d%d",&in[i].dl,&in[i].dr,&in[i].ul,&in[i].ur);
        S.insert(in[i].ul), S.insert(in[i].ur);
    }
    sort(in+1,in+n+1,cmp);

    M[0]=++M_len;
    for(set<int>::iterator it=S.begin(); it!=S.end(); it++) M[*it]=++M_len;
    for(nn=1; nn<M_len; nn*=2);
    for(int i=1; i<=n; i++)
        in[i].ul=M[in[i].ul], in[i].ur=M[in[i].ur];

    tree[nn]={0,1}, update(nn/2);
    for(int i=1; i<=n; i++){
        while(Q.empty()==false && Q.top().first<=in[i].dl){
            int x=Q.top().second;
            tree[nn+in[x].ur-1]=add(tree[nn+in[x].ur-1],d[x]);
            update((nn+in[x].ur-1)/2), Q.pop();
        }
        d[i]=get(1,1,nn,1,in[i].ul), d[i].first++;
        Q.push({in[i].dr,i});
    }

    for(int i=1; i<=n; i++) out=add(out,d[i]);
    printf("%d %d",out.first,out.second);
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:42:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:44:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&in[i].dl,&in[i].dr,&in[i].ul,&in[i].ur);
                                                                  ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 5 ms 1040 KB Output is correct
6 Correct 7 ms 1404 KB Output is correct
7 Correct 9 ms 1736 KB Output is correct
8 Correct 14 ms 2160 KB Output is correct
9 Correct 29 ms 3816 KB Output is correct
10 Correct 57 ms 6620 KB Output is correct
11 Correct 69 ms 8444 KB Output is correct
12 Correct 181 ms 16012 KB Output is correct
13 Correct 207 ms 19936 KB Output is correct
14 Correct 242 ms 24368 KB Output is correct
15 Correct 307 ms 27676 KB Output is correct
16 Correct 343 ms 31144 KB Output is correct
17 Correct 335 ms 34692 KB Output is correct
18 Correct 286 ms 38040 KB Output is correct
19 Correct 332 ms 41756 KB Output is correct
20 Correct 395 ms 45840 KB Output is correct