답안 #33619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
33619 2017-10-30T16:09:10 Z top34051 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
436 ms 42728 KB
#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

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);
                                                                        ^
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 17648 KB Output is correct
2 Correct 6 ms 17648 KB Output is correct
3 Correct 3 ms 17780 KB Output is correct
4 Correct 9 ms 17912 KB Output is correct
5 Correct 6 ms 18176 KB Output is correct
6 Correct 13 ms 18440 KB Output is correct
7 Correct 13 ms 18704 KB Output is correct
8 Correct 13 ms 18968 KB Output is correct
9 Correct 29 ms 20156 KB Output is correct
10 Correct 79 ms 22664 KB Output is correct
11 Correct 76 ms 23852 KB Output is correct
12 Correct 173 ms 30188 KB Output is correct
13 Correct 226 ms 32696 KB Output is correct
14 Correct 319 ms 35204 KB Output is correct
15 Correct 396 ms 36392 KB Output is correct
16 Correct 426 ms 37712 KB Output is correct
17 Correct 413 ms 38900 KB Output is correct
18 Correct 376 ms 40220 KB Output is correct
19 Correct 373 ms 41408 KB Output is correct
20 Correct 436 ms 42728 KB Output is correct