Submission #963037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963037	2024-04-14T11:48:42 Z	hariaakas646	Zoltan (COCI16_zoltan)	C++14	21 / 140	817 ms	50508 KB

zoltan

#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]);
      |         ^~~

Subtask #1

21.0 / 140.0

#	Verdict	Execution time	Memory	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