Submission #41121

#	Time	Username	Problem	Language	Result	Execution time	Memory
41121		14kg	trapezoid (balkan11_trapezoid)	C++11	100 / 100	395 ms	45840 KiB

trapezoid

#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 (stderr)

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 / 100