oj.uz

답안 #97687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97687 2019-02-17T17:59:16 Z Abelyan 사다리꼴 (balkan11_trapezoid) C++17
65 / 100
 330 ms 62140 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define fr first
#define sc second
#define pir pair<int,int>

const int N=1e5+6;
const int MOD=30013;

bool dzn(char k){
    if (k=='a' || k=='o' || k=='i' || k=='u' || k=='e')return true;
    return false;
}


struct node{
    int sum,mx;
} dp[N],sg[4*N];

node operator +(const node &firstNode,const node &secondNode){
    node c;
    if (firstNode.mx>secondNode.mx)return firstNode;
    else if (secondNode.mx>firstNode.mx) return secondNode;
    c.sum=(firstNode.sum+secondNode.sum)%MOD;
    c.mx=max(firstNode.mx,secondNode.mx);
    return c;
}

void update(int v,int tl,int tr,int ind,node del){
    if (tl==tr){
        sg[v]=del;
        return;
    }
    int tm=(tl+tr)/2;
    if (ind<=tm){
        update(v+v,tl,tm,ind,del);
    }
    else{
        update(v+v+1,tm+1,tr,ind,del);
    }
    sg[v]=sg[v+v]+sg[v+v+1];
}

node get(int v,int tl,int tr,int l,int r){
    if (l>r) return {0,0};
    if (tl==l && tr==r){
        return sg[v];
    }
    int tm=(tl+tr)/2;
    return get(v+v,tl,tm,l,min(tm,r))+get(v+v+1,tm+1,tr,max(tm+1,l),r);
}


int a[N],b[N],c[N],d[N];
map <int,int> mp;
int ver[N];
vector<int> buck[N];



int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    set<int> s;
    vector<pair<pir,pir> > v;
    FOR(i,n){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        s.insert(c[i]);
        s.insert(d[i]);
    }
    int qan=0;
    trav (tv,s){
        mp[tv]=qan++;
    }
    FOR(i,n){
        c[i]=mp[c[i]];
        d[i]=mp[d[i]];
        v.push_back({{b[i],a[i]},{c[i],d[i]}});
    }
    sort(v.begin(),v.end());
    vector<int> bin;
    FOR(i,n){
        dp[i]={1,1};
        buck[lower_bound(bin.begin(),bin.end(),v[i].fr.sc)-bin.begin()-1].push_back(i);
        bin.push_back(v[i].fr.fr);
    }
    FOR(i,n){
        update(1,0,qan-1,v[i].sc.sc,dp[i]);
        trav(tv,buck[i]){
            node cur=get(1,0,qan-1,0,v[tv].sc.fr);
            cur.mx++;
            //cout<<dp[tv].sum<<" "<<dp[tv].mx<<endl;
            dp[tv]=dp[tv]+cur;
            //cout<<dp[tv].sum<<" "<<cur.mx<<endl;
        }
    }
    node ans=get(1,0,qan-1,0,qan-1);
    cout<<ans.mx<<" "<<ans.sum<<endl;
    return 0;
}

Subtask #1
65.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 3072 KB Output is correct
5 Correct 9 ms 3328 KB Output is correct
6 Correct 12 ms 3712 KB Output is correct
7 Correct 12 ms 3968 KB Output is correct
8 Correct 14 ms 4352 KB Output is correct
9 Correct 39 ms 5880 KB Output is correct
10 Correct 50 ms 9200 KB Output is correct
11 Correct 68 ms 10480 KB Output is correct
12 Correct 167 ms 18272 KB Output is correct
13 Correct 180 ms 21204 KB Output is correct
14 Runtime error 211 ms 47972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 282 ms 50812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 328 ms 52912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 290 ms 54700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 278 ms 57568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 269 ms 57956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 330 ms 62140 KB Execution killed with signal 11 (could be triggered by violating memory limits)