Submission #853408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853408	2023-09-24T09:42:57 Z	hariaakas646	San (COCI17_san)	C++17	96 / 120	342 ms	65536 KB

san

#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define scld(t) scanf("%ld", &t)
#define sclld(t) scanf("%lld", &t)
#define scc(t) scanf("%c", &t)
#define scs(t) scanf("%s", t)
#define scf(t) scanf("%f", &t)
#define sclf(t) scanf("%lf", &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 int li;
typedef unsigned long int uli;
typedef long long int lli;
typedef unsigned long long int ulli;
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);
}

template <class T>
struct BIT
{
    int size;
    vector<T> bit;
    vector<T> vec;

    BIT(int n) : size(n), bit(n + 1), vec(n + 1) {}

    int lsb(int x)
    {
        return x & (-x);
    }

    void set(int id, T v)
    {
        add(id, v - vec[id]);
    }

    void add(int id, T v)
    {
        if (id == 0)
            return;
        vec[id] += v;
        while (id <= size)
        {
            bit[id] += v;
            id += lsb(id);
        }
    }

    T query(int id)
    {
        T tot = 0;
        if (id == 0)
            return tot;
        while (id >= 1)
        {
            tot += bit[id];
            id -= lsb(id);
        }
        return tot;
    }
};

int main() {
    // usaco();
    int n;
    lli k;
    scd(n);
    sclld(k);

    vector<pair<lli, lli>> v1(n/2), v2((n+1)/2);
    frange(i, n/2) {sclld(v1[i].f); sclld(v1[i].s);}
    frange(i, (n+1)/2) {sclld(v2[i].f); sclld(v2[i].s);}

    vector<pair<lli, lli>> val1, val2;
    // val1.pb(mp(0, 0));
    // val2.pb(mp(1e18, 0));
    vll av;
    // av.pb(0LL);
    // av.pb(k);

    frange(i, 1<<(n/2)) {
        lli pre = 0;
        lli tot = 0;
        bool done = true;
        frange(j, n/2) {
            if(i & (1<<j)) {
                if(v1[j].f < pre) {
                    done = false;
                    break;
                }
                pre = v1[j].f;
                tot += v1[j].s;
            }
        }
        if(done) {val1.pb(mp(pre, k-tot)); av.pb(k-tot);}
    }

    frange(i, 1<<(((n+1)/2))) {
        lli pre = 0;
        lli tot = 0;
        lli fir = 1e18;
        bool done = true;
        frange(j, (n+1)/2) {
            if(i & (1<<j)) {
                if(v2[j].f < pre) {
                    done = false;
                    break;
                }
                if(fir == 1e18) fir = v2[j].f;
                pre = v2[j].f;
                tot += v2[j].s;
            }
        }
        if(done) {val2.pb(mp(fir, tot)); av.pb(tot);}
    }
    sort(all(av), greater<lli>());
    sort(all(val1), greater<>());
    sort(all(val2), greater<>());
    map<lli, int> pos;
    frange(i, av.size()) {
        pos[av[i]] = i+1;
    }

    BIT<lli> bit(av.size()+10);

    lli id = 0;
    int x = val2.size();
    // printf("%d\n", x);
    lli tot = 0;
    for(auto p : val1) {
        // printf("%lld %lld\n", p.f, p.s);
        for(; id<x; id++) {
            if(val2[id].f < p.f) break;
            // printf("%lld %lld %d\n", val2[id].f, val2[id].s, pos[val2[id].s]);
            bit.add(pos[val2[id].s], 1);
        }
        tot += bit.query(pos[p.s]);

    }
    printf("%lld", tot);
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define forr(i, j, k) for (int i = j; i < k; i++)
      |                                         ^
san.cpp:13:22: note: in expansion of macro 'forr'
   13 | #define frange(i, j) forr(i, 0, j)
      |                      ^~~~
san.cpp:143:5: note: in expansion of macro 'frange'
  143 |     frange(i, av.size()) {
      |     ^~~~~~
san.cpp: In function 'void usaco()':
san.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
san.cpp: In function 'int main()':
san.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)
      |                ~~~~~^~~~~~~~~~
san.cpp:90:5: note: in expansion of macro 'scd'
   90 |     scd(n);
      |     ^~~
san.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
san.cpp:91:5: note: in expansion of macro 'sclld'
   91 |     sclld(k);
      |     ^~~~~
san.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
san.cpp:94:21: note: in expansion of macro 'sclld'
   94 |     frange(i, n/2) {sclld(v1[i].f); sclld(v1[i].s);}
      |                     ^~~~~
san.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
san.cpp:94:37: note: in expansion of macro 'sclld'
   94 |     frange(i, n/2) {sclld(v1[i].f); sclld(v1[i].s);}
      |                                     ^~~~~
san.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
san.cpp:95:25: note: in expansion of macro 'sclld'
   95 |     frange(i, (n+1)/2) {sclld(v2[i].f); sclld(v2[i].s);}
      |                         ^~~~~
san.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
san.cpp:95:41: note: in expansion of macro 'sclld'
   95 |     frange(i, (n+1)/2) {sclld(v2[i].f); sclld(v2[i].s);}
      |                                         ^~~~~

Subtask #1

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	10440 KB	Output is correct
2	Correct	4 ms	860 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	19568 KB	Output is correct
2	Correct	22 ms	3024 KB	Output is correct

Subtask #5

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	342 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-