oj.uz

답안 #526834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526834 2022-02-16T08:42:58 Z BackNoob 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 121 ms 8688 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 30013;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct item {
    int x, y, u, v;
} a[mxN];

struct seg
{
    int l, r, ok , idx;
    bool operator<(seg a)
    {
        if(l == a.l && r == a.r) return ok > a.ok;
        if(l == a.l) return r < a.r;
        return l < a.l;
    }
};

int n;
int f[mxN];
int g[mxN];

void add(int &a , int b)
{
    a += b;
    if(a >= mod) a -= mod;
}

int bitadd[mxN * 2];
void updateadd(int pos, int val)
{
    for(; pos <= 2 * n ; pos += pos & -pos) add(bitadd[pos] , val);
}
int getsum(int pos)
{
    int res = 0;
    for(; pos > 0 ; pos -= pos & -pos) add(res , bitadd[pos]);
    return res;
}

int getsum(int l , int r)
{
    int res = getsum(r) - getsum(l - 1);
    if(res < 0) res += mod;
}

int bitmax[mxN * 2];
void updatemax(int pos, int val)
{
    for(; pos <= n * 2 ; pos += pos & -pos) maximize(bitmax[pos] , val);
}
int getmax(int pos)
{
    int res = 0;
    for(; pos > 0 ; pos -= pos & -pos) maximize(res , bitmax[pos]);
    return res;
}

vector<int> cpx , cpy;

void solve()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
        cpx.pb(a[i].x);
        cpy.pb(a[i].y);
        cpx.pb(a[i].u);
        cpy.pb(a[i].v);
    }

    sort(all(cpx));
    cpx.erase(unique(all(cpx)) , cpx.end());
    sort(all(cpy));
    cpy.erase(unique(all(cpy)) , cpy.end());

    for(int i = 1 ; i <= n ; i++) {
        a[i].x = lower_bound(all(cpx) , a[i].x) - cpx.begin() + 1;
        a[i].y = lower_bound(all(cpy) , a[i].y) - cpy.begin() + 1;
        a[i].u = lower_bound(all(cpx) , a[i].u) - cpx.begin() + 1;
        a[i].v = lower_bound(all(cpy) , a[i].v) - cpy.begin() + 1;
    }

    vector<seg> val;
    for(int i = 1 ; i <= n ; i++)
    {
        val.pb({a[i].x , a[i].y , 1 , i});
        val.pb({a[i].u , a[i].v , 0 , i});
    }
    sort(all(val));

    for(auto it : val)
    {
        int i = it.idx;
        if(it.ok == 0) {
            //cout << it.r << ' ' << f[i] << ' ' << g[i] << endl;
            if(f[i] == 0) {
                f[i] = g[i] = 1;
            }
            updatemax(it.r , f[i]);
            updateadd(f[i] , g[i]);
        }
        else {
            f[i] = max(1 , getmax(it.r - 1) + 1);
            if(f[i] == 1) g[i] = 1;
            else g[i] = getsum(f[i] - 1 , f[i] - 1);
        }
    }

    int res = getmax(2 * n);
    int ans = getsum(res , res);
    cout << res << ' ' << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--)
    {
        solve();
    }
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int getsum(int, int)':
trapezoid.cpp:71:1: warning: no return statement in function returning non-void [-Wreturn-type]
   71 | }
      | ^

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 580 KB Execution killed with signal 11
2 Runtime error 2 ms 588 KB Execution killed with signal 11
3 Runtime error 3 ms 628 KB Execution killed with signal 11
4 Runtime error 3 ms 716 KB Execution killed with signal 11
5 Runtime error 4 ms 904 KB Execution killed with signal 11
6 Runtime error 6 ms 1004 KB Execution killed with signal 11
7 Runtime error 8 ms 1096 KB Execution killed with signal 11
8 Runtime error 7 ms 1332 KB Execution killed with signal 11
9 Runtime error 15 ms 1800 KB Execution killed with signal 11
10 Runtime error 24 ms 2852 KB Execution killed with signal 11
11 Runtime error 28 ms 3188 KB Execution killed with signal 11
12 Runtime error 59 ms 4480 KB Execution killed with signal 11
13 Runtime error 65 ms 5452 KB Execution killed with signal 11
14 Runtime error 81 ms 7756 KB Execution killed with signal 11
15 Runtime error 92 ms 7840 KB Execution killed with signal 11
16 Runtime error 95 ms 8040 KB Execution killed with signal 11
17 Runtime error 105 ms 8228 KB Execution killed with signal 11
18 Runtime error 102 ms 8368 KB Execution killed with signal 11
19 Runtime error 121 ms 8484 KB Execution killed with signal 11
20 Runtime error 115 ms 8688 KB Execution killed with signal 11