답안 #963037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963037 2024-04-14T11:48:42 Z hariaakas646 Zoltan (COCI16_zoltan) C++14
21 / 140
817 ms 50508 KB
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

const lli mod = 1e9 + 7;

struct Data {
    int len = -1e9;
    lli cnt = 0;
};

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;
    vi lazy;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
        lazy = vi(2*size, 0);
    }

    T operation(T x, T y)
    {
        T out;
        if(x.len > y.len) {
            out = x;
        }
        else if(y.len > x.len) {
            out = y;
        }
        else {
            out = x;
            out.cnt += y.cnt;
            out.cnt %= mod;
        }
        return out;
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void propagate(int x, int l, int r)
    {
        segtree[x].len += lazy[x];
        if (l < r)
        {
            lazy[2 * x + 1] += lazy[x];
            lazy[2 * x + 2] += lazy[x];
        }
        lazy[x] = 0;
    }

    void update(int x, int l, int r, int id, T val)
    {
        propagate(x, l, r);
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        propagate(2*x+1, l, mid);
        propagate(2*x+2, mid+1, r);
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
        if(lx > rx) return def;
        return query(0, 0, size - 1, lx, rx);
    }

    void update2(int x, int l, int r, int lx, int rx, int val)
    {
        propagate(x, l, r);
        if (lx <= l && r <= rx)
        {
            lazy[x] += val;
            return;
        }
        int mid = (l + r) / 2;
        if (lx <= mid)
        {
            update2(2 * x + 1, l, mid, lx, rx, val);
        }
        if (rx >= mid + 1)
        {
            update2(2 * x + 2, mid + 1, r, lx, rx, val);
        }
        propagate(2 * x + 1, l, mid);
        propagate(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void update2(int lx, int rx, int val)
    {
        if(lx > rx) return;
        update2(0, 0, size - 1, lx, rx, val);
    }
};

int main() {
    // usaco();
    int n;
    scd(n);

    SegTree<Data> seg1, seg2;
    Data tmp;
    seg1.init(n+2, tmp);
    seg2.init(n+2, tmp);
    tmp.len = 0;
    tmp.cnt = 1;
    seg1.set(0, tmp);
    seg2.set(n+1, tmp);
    seg1.build(); seg2.build();
    vi vec(n);

    seti st;
    frange(i, n) {
        scd(vec[i]);
        st.insert(vec[i]);
    }

    mpii mv;
    int id = 1;
    for(auto e : st) mv[e] = id++;

    frange(i, n) {
        int v = mv[vec[i]];
        Data out = seg1.query(0, v-1);
        out.len++;
        
        Data og = seg1.query(v, v);
        if(out.len < og.len) {
            out = og;
        }
        else if(out.len == og.len) {
            out.cnt += og.cnt;
            out.cnt %= mod;
        }
        
        seg1.update(v, out);
        seg2.update2(1, v-1, 1);
        out = seg2.query(v+1, n+1);

        out.len++;
        
        og = seg2.query(v, v);
        if(out.len < og.len) {
            out = og;
        }
        else if(out.len == og.len) {
            out.cnt += og.cnt;
            out.cnt %= mod;
        }
        
        seg2.update(v, out);
        seg1.update2(v+1, n, 1);
    }

    Data v1 = seg1.query(1, n);
    Data v2 = seg2.query(1, n);
    Data out;
    if(v1.len > v2.len) {
        out = v1;
    }
    else if(v2.len > v1.len) {
        out = v2;
    }
    else {
        out.len = v1.len;
        out.cnt = (v1.cnt + v2.cnt)%mod;
    }
    if(st.size() == 1) {
        lli out = n;
        forr(i, 1, n) {
            out *= 2;
            out %= mod;
        }
        printf("1 %lld", out);
    }
    else
    printf("%d %lld", v1.len, v1.cnt);
}

Compilation message

zoltan.cpp: In function 'void usaco()':
zoltan.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
zoltan.cpp:201:5: note: in expansion of macro 'scd'
  201 |     scd(n);
      |     ^~~
zoltan.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
zoltan.cpp:216:9: note: in expansion of macro 'scd'
  216 |         scd(vec[i]);
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 2 ms 604 KB Output isn't correct
8 Incorrect 3 ms 604 KB Output isn't correct
9 Incorrect 3 ms 604 KB Output isn't correct
10 Incorrect 2 ms 604 KB Output isn't correct
11 Runtime error 489 ms 45792 KB Memory limit exceeded
12 Runtime error 463 ms 43640 KB Memory limit exceeded
13 Incorrect 386 ms 28408 KB Output isn't correct
14 Runtime error 565 ms 43984 KB Memory limit exceeded
15 Runtime error 730 ms 47588 KB Memory limit exceeded
16 Runtime error 817 ms 50508 KB Memory limit exceeded
17 Runtime error 645 ms 46696 KB Memory limit exceeded
18 Runtime error 610 ms 46924 KB Memory limit exceeded
19 Runtime error 618 ms 46940 KB Memory limit exceeded
20 Runtime error 642 ms 47128 KB Memory limit exceeded