oj.uz

답안 #526838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526838 2022-02-16T08:50:27 Z BackNoob 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 118 ms 7800 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 && ok == a.ok) return idx < a.idx;
        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(int i = 1 ; i <= n ; i++) {
        if(a[i].x > a[i].u || a[i].y > a[i].v) {
            cout << -1;
            exit(0);
        }
    }

    for(auto it : val)
    {
        int i = it.idx;
        if(it.ok == 0) {
            //cout << it.r << ' ' << f[i] << ' ' << g[i] << endl;
            if(it.r == 0) {
                cout << -1;
                exit(0);
            }
            if(f[i] == 0) {
                cout << -1;
                exit(0);
            }
            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 588 KB Execution killed with signal 11
2 Runtime error 2 ms 588 KB Execution killed with signal 11
3 Runtime error 3 ms 588 KB Execution killed with signal 11
4 Runtime error 3 ms 716 KB Execution killed with signal 11
5 Runtime error 4 ms 972 KB Execution killed with signal 11
6 Runtime error 5 ms 1004 KB Execution killed with signal 11
7 Runtime error 8 ms 1100 KB Execution killed with signal 11
8 Runtime error 8 ms 1328 KB Execution killed with signal 11
9 Runtime error 17 ms 1664 KB Execution killed with signal 11
10 Runtime error 27 ms 2500 KB Execution killed with signal 11
11 Runtime error 33 ms 2856 KB Execution killed with signal 11
12 Runtime error 54 ms 4148 KB Execution killed with signal 11
13 Runtime error 67 ms 4912 KB Execution killed with signal 11
14 Runtime error 78 ms 6840 KB Execution killed with signal 11
15 Runtime error 89 ms 6996 KB Execution killed with signal 11
16 Runtime error 108 ms 7188 KB Execution killed with signal 11
17 Runtime error 95 ms 7316 KB Execution killed with signal 11
18 Runtime error 93 ms 7472 KB Execution killed with signal 11
19 Runtime error 106 ms 7636 KB Execution killed with signal 11
20 Runtime error 118 ms 7800 KB Execution killed with signal 11