Submission #33619

#	Time	Username	Problem	Language	Result	Execution time	Memory
33619		top34051	trapezoid (balkan11_trapezoid)	C++14	100 / 100	436 ms	42728 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mod 30013
#define maxn 200010
struct node {
    int a,b,c,d;
};
int n,szx,szy;
pii val[maxn];
pii tree[maxn];
node p[maxn];
vector<int> ass[maxn];
vector<int> hole[maxn];
map<int,int> mpx;
map<int,int> mpy;
void cpidx() {
    int i;
    map<int,int>::iterator it;
    for(i=1;i<=n;i++) mpx[p[i].a], mpx[p[i].b];
    for(i=1;i<=n;i++) mpy[p[i].c], mpy[p[i].d];
    for(it=mpx.begin();it!=mpx.end();++it) it->second = ++szx;
    for(it=mpy.begin();it!=mpy.end();++it) it->second = ++szy;
    for(i=1;i<=n;i++) p[i].a = mpx[p[i].a], p[i].b = mpx[p[i].b];
    for(i=1;i<=n;i++) p[i].c = mpy[p[i].c], p[i].d = mpy[p[i].d];
}
pii combine(pii x,pii y) {
    if(x.first==y.first) return {x.first,(x.second+y.second+mod)%mod};
    if(x.first>y.first) return x;
    return y;
}
void add(int x,pii val) {
    while(x>0) {
        tree[x] = combine(tree[x],val);
        x -= x&-x;
    }
}
pii query(int x) {
    pii ans;
    ans = {0,0};
    while(x<=szy+5) {
        ans = combine(ans,tree[x]);
        x += x&-x;
    }
    return ans;
}
main() {
    int i,x,pos;
    pii ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d);
    cpidx();
    for(i=1;i<=n;i++) ass[p[i].a].push_back(i), hole[p[i].b].push_back(i);
    add(szy+1,{0,1});
    for(pos=szx;pos>0;pos--) {
//        printf("TIME = %d\n",pos);
        for(i=0;i<ass[pos].size();i++) {
            x = ass[pos][i];
//            printf("------ add %d {%d, %d}\n",x,val[x].first,val[x].second);
            add(p[x].c,val[x]);
        }
        for(i=0;i<hole[pos].size();i++) {
            x = hole[pos][i];
            val[x] = query(p[x].d+1);
            val[x].first++;
//            printf("---------------------- val %d = {%d, %d}\n",x,val[x].first,val[x].second);
        }
    }
    ans = query(1);
    printf("%d %d",ans.first,ans.second);
}

Compilation message (stderr)

trapezoid.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<ass[pos].size();i++) {
                  ^
trapezoid.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<hole[pos].size();i++) {
                  ^
trapezoid.cpp:50:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:51:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d);
                                                                        ^

• Subtask 1: 100 / 100