oj.uz

답안 #1007635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007635 2024-06-25T09:34:19 Z doducanh 사다리꼴 (balkan11_trapezoid) C++14
45 / 100
 500 ms 9144 KB 
#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
const int maxn=1e5+7;
const int mod=30013;
const int maxx=1e9+7;
void cmax(pair<int,int>&a,pair<int,int>b)
{
    if(a.fi<b.fi)a=b;
    else{
        if(a.fi==b.fi&&a.fi!=0)a.se=(a.se+b.se)%mod;
    }
}
int id(int x,vector<pair<int,int>>tmp)
{
    return lower_bound(tmp.begin(),tmp.end(),make_pair(x,-maxx))-tmp.begin()+1;
}
struct BIT
{
private:
    int n;
    vector<pair<int,int>>t;
public:
    BIT(){}
    BIT(int n):n(n),t(n+7,make_pair(0,1)){}
    void up(int x,pair<int,int> val){
        for(;x<n;x+=(x&(-x)))cmax(t[x],val);
    }
    pair<int,int>get(int x)
    {
        if(x<=0)return {0,1};
        pair<int,int>res={0,1};
        for(;x;x-=(x&(-x)))cmax(res,t[x]);
        return res;
    }
};
vector<int>a,b,c,d;
int n;
pair<int,int>ans[maxn];
main()
{
    cin>>n;
    a.resize(n+1);b.resize(n+1);
    c.resize(n+1);d.resize(n+1);
    vector<pair<int,int>>top;
    vector<pair<int,int>>bot;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        top.push_back({a[i],i});
        top.push_back({b[i],i});
        bot.push_back({c[i],i});
        bot.push_back({d[i],i});
    }
    sort(begin(top),end(top));
    sort(begin(bot),end(bot));
    bot.erase(unique(begin(bot),end(bot)),end(bot));
    BIT t(bot.size());
    for(auto[x,i]:top){
        if(x==a[i]){
            pair<int,int>tmp=t.get(id(c[i],bot)-1);
            ans[i]={tmp.fi+1,tmp.se};
        }
        else if(x==b[i]){
            t.up(id(d[i],bot),ans[i]);
        }
    }
    pair<int,int>res={0,0};
    for(int i=1;i<=n;i++){
        cmax(res,ans[i]);
    }
    cout<<res.fi<<" "<<res.se;
    return 0;
}

Compilation message

trapezoid.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto[x,i]:top){
      |             ^

Subtask #1
45.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 14 ms 600 KB Output is correct
6 Correct 27 ms 604 KB Output is correct
7 Correct 46 ms 792 KB Output is correct
8 Correct 72 ms 1012 KB Output is correct
9 Correct 279 ms 1504 KB Output is correct
10 Execution timed out 1030 ms 2676 KB Time limit exceeded
11 Execution timed out 1084 ms 2956 KB Time limit exceeded
12 Execution timed out 1064 ms 5748 KB Time limit exceeded
13 Execution timed out 1071 ms 5824 KB Time limit exceeded
14 Execution timed out 1062 ms 7432 KB Time limit exceeded
15 Execution timed out 1063 ms 7352 KB Time limit exceeded
16 Execution timed out 1061 ms 7096 KB Time limit exceeded
17 Execution timed out 1072 ms 8584 KB Time limit exceeded
18 Execution timed out 1066 ms 7608 KB Time limit exceeded
19 Execution timed out 1062 ms 8008 KB Time limit exceeded
20 Execution timed out 1060 ms 9144 KB Time limit exceeded