oj.uz

답안 #167217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167217 2019-12-06T16:57:00 Z rzbt 사다리꼴 (balkan11_trapezoid) C++14
34 / 100
 500 ms 50048 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

int n;
pair<pair<int,int>, pair<int,int> > niz[MAXN];
set<int> sg,sd;
map<int,int> mg,md;
pair<int,int>  ubaci[2*MAXN],pitaj[2*MAXN];
pair<int,int> seg[8*MAXN];
pair<int,int> tres[MAXN];
pair<int,int> res;

void dodaj(int l,int d,int p,int k,pair<int,int> x){

    if(l==d){
        seg[k]=x;
        return;
    }
    int mid=(l+d)/2;
    if(p<=mid)dodaj(l,mid,p,k+k,x);
    else dodaj(mid+1,d,p,k+k+1,x);
    if(seg[k+k].F==seg[k+k+1].F)seg[k]=mp(seg[k+k].F,seg[k+k].S+seg[k+k+1].S);
    else seg[k]=max(seg[k+k],seg[k+k+1]);
    //printf("    %d %d %d\n",k,seg[k].F,seg[k].S);
}

pair<int,int> dobij(int l,int d,int tl,int td,int k){
    if(l>td || d<tl)return mp(0,0);
    if(l>=tl && d<=td)return seg[k];
    int mid=(l+d)/2;
    auto levo=dobij(l,mid,tl,td,k+k);
    auto desno=dobij(mid+1,d,tl,td,k+k+1);
    //printf("%d %d\n",levo.F,desno.F);
    if(levo.F==desno.F)return mp(levo.F,levo.S+desno.S);
    return max(levo,desno);
}



int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        niz[i]=mp(mp(a,b),mp(c,d));
        sg.insert(a);
        sg.insert(b);
        sd.insert(c);
        sd.insert(d);
    }
    int brojac=1;
    for(auto x:sg){
        mg[x]=brojac;
        brojac++;
    }
    brojac=1;
    for(auto x:sd){
        md[x]=brojac;
        brojac++;
    }
    for(int i=1;i<=n;i++){
        niz[i].F.F=mg[niz[i].F.F];
        niz[i].F.S=mg[niz[i].F.S];
        niz[i].S.F=md[niz[i].S.F];
        niz[i].S.S=md[niz[i].S.S];
        pitaj[niz[i].F.F]=mp(niz[i].S.F,i);
        ubaci[niz[i].F.S]=mp(niz[i].S.S,i);
    }
    for(int i=1;i<=n+n;i++){
        //printf("   %d %d",seg[1])
        if(pitaj[i].F){

            pair<int,int> ans=dobij(1,n+n,1,pitaj[i].F,1);
            if(ans==mp(0,0))ans=mp(0,1);

            ans.F++;

            tres[pitaj[i].S]=ans;
            if(ans.F>res.F)
                res=ans;
            else if(ans.F==res.F)
                res.S+=ans.S;
            }else{

                dodaj(1,n+n,ubaci[i].F,1,tres[ubaci[i].S]);
            }

    }
    printf("%d %d",res.F,res.S);

    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a, &b, &c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Partially correct 4 ms 672 KB Partially correct
4 Partially correct 5 ms 760 KB Partially correct
5 Partially correct 8 ms 1400 KB Partially correct
6 Partially correct 11 ms 1784 KB Partially correct
7 Partially correct 14 ms 2296 KB Partially correct
8 Partially correct 20 ms 2936 KB Partially correct
9 Partially correct 46 ms 5436 KB Partially correct
10 Partially correct 96 ms 10616 KB Partially correct
11 Partially correct 121 ms 12864 KB Partially correct
12 Partially correct 287 ms 25404 KB Partially correct
13 Partially correct 354 ms 29944 KB Partially correct
14 Partially correct 433 ms 36592 KB Partially correct
15 Execution timed out 524 ms 38948 KB Time limit exceeded
16 Execution timed out 567 ms 41080 KB Time limit exceeded
17 Execution timed out 545 ms 43520 KB Time limit exceeded
18 Execution timed out 529 ms 45560 KB Time limit exceeded
19 Execution timed out 547 ms 47096 KB Time limit exceeded
20 Execution timed out 652 ms 50048 KB Time limit exceeded