oj.uz

답안 #526842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526842 2022-02-16T09:09:22 Z BackNoob 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 116 ms 7640 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;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(ll l , ll r) {
    return l + rd() * 1LL * rd() % (r - l + 1);
}

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> valx , valy;

void solve()
{
//    n = Rand(2 , 3);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
//        a[i].x = Rand(1 , 10);
//        a[i].y = Rand(1 , 10);
//        a[i].u = Rand(a[i].x , 20);
//        a[i].v = Rand(a[i].y , 20);
        valx.pb(a[i].x);
        valy.pb(a[i].y);
        valx.pb(a[i].u);
        valy.pb(a[i].v);
    }

    //cout << n << endl;
    //for(int i = 1 ; i <= n ; i++)
    //    cout << a[i].x << ' ' << a[i].u << ' ' << a[i].y << ' ' << a[i].v << endl;

    sort(all(valx));
    valx.erase(unique(all(valx)) , valx.end());
    sort(all(valy));
    valy.erase(unique(all(valy)) , valy.end());

    for(int i = 1 ; i <= n ; i++) {
        a[i].x = lower_bound(all(valx) , a[i].x) - valx.begin() + 1;
        a[i].y = lower_bound(all(valy) , a[i].y) - valy.begin() + 1;
        a[i].u = lower_bound(all(valx) , a[i].u) - valx.begin() + 1;
        a[i].v = lower_bound(all(valy) , a[i].v) - valy.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) {
                cout << -1 << ' ' << -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:77:1: warning: no return statement in function returning non-void [-Wreturn-type]
   77 | }
      | ^

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Incorrect 3 ms 460 KB Output isn't correct
6 Incorrect 3 ms 716 KB Output isn't correct
7 Incorrect 4 ms 716 KB Output isn't correct
8 Incorrect 5 ms 844 KB Output isn't correct
9 Incorrect 10 ms 1352 KB Output isn't correct
10 Incorrect 21 ms 2236 KB Output isn't correct
11 Incorrect 32 ms 2364 KB Output isn't correct
12 Incorrect 59 ms 4068 KB Output isn't correct
13 Incorrect 66 ms 4332 KB Output isn't correct
14 Incorrect 74 ms 6696 KB Output isn't correct
15 Incorrect 82 ms 6864 KB Output isn't correct
16 Incorrect 94 ms 7012 KB Output isn't correct
17 Incorrect 100 ms 7292 KB Output isn't correct
18 Incorrect 95 ms 7344 KB Output isn't correct
19 Incorrect 116 ms 7436 KB Output isn't correct
20 Incorrect 107 ms 7640 KB Output isn't correct