oj.uz

답안 #972226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972226 2024-04-30T09:00:09 Z hariaakas646 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 205 ms 30404 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);
}

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;
    }
};

vi out;
BIT<lli> bit2(0);
vector<pair<pii, pair<int, lli>>> upd;

void rec(int l, int r, vector<pair<pair<int, lli>, pii>> quer) {
    if(l == r) {
        for(auto p : quer) {
            if(p.s.s >= l) {
                out[p.s.f] = upd[l].s.f;
            }
            else {
                out[p.s.f] = 0;
            }
        }
        return;
    }
    int mid = (l+r)/2;
    forr(i, l, mid+1) {
        auto p = upd[i];
        bit2.add(p.f.f, p.s.s);
        bit2.add(p.f.s+1, -p.s.s);
    }
    vector<pair<pair<int, lli>, pii>> lv, rv;
    for(auto p : quer) {
        lli v = bit2.query(p.f.f);
        if(v >= p.f.s) {
            lv.pb(p);
        }
        else {
            rv.pb(mp(mp(p.f.f, p.f.s-v), p.s));
        }
    }
    forr(i, l, mid+1) {
        auto p = upd[i];
        bit2.add(p.f.f, -p.s.s);
        bit2.add(p.f.s+1, +p.s.s);
    }
    rec(l, mid, lv);
    rec(mid+1, r, rv);
}

int main() {
    // usaco();
    int n, m, q;
    scd(n);
    scd(m);
    scd(q);

    BIT<lli> bit(n+1);
    BIT<lli> bitv(n+1);

    vector<pair<pair<int, lli>, pii>> quer;
    

    frange(i, q) {
        int t;
        scd(t);

        if(t == 1) {
            int l, r, c;
            lli k;
            scd(l);
            scd(r);
            scd(c);
            sclld(k);
            upd.pb(mp(mp(l, r), mp(c, k)));
        }
        else if(t == 2) {
            int l, r;
            lli k;
            scd(l);
            scd(r);
            sclld(k);
            bit.add(l, k);
            bit.add(r+1, -k);
        }
        else {
            int a;
            lli b;
            scd(a);
            sclld(b);
            b += bit.query(a);
            quer.pb(mp(mp(a, b), mp(quer.size(), upd.size()-1)));
        }
    }
    upd.pb(mp(mp(0, 0), mp(0, 0LL)));
    bit2 = BIT<lli>(n+1);
    out = vi(quer.size());
    rec(0, upd.size()-1, quer);

    for(auto e : out) printf("%d\n", e);
}

Compilation message

foodcourt.cpp: In function 'void usaco()':
foodcourt.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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'int main()':
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:123:5: note: in expansion of macro 'scd'
  123 |     scd(n);
      |     ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:124:5: note: in expansion of macro 'scd'
  124 |     scd(m);
      |     ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:125:5: note: in expansion of macro 'scd'
  125 |     scd(q);
      |     ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:135:9: note: in expansion of macro 'scd'
  135 |         scd(t);
      |         ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:140:13: note: in expansion of macro 'scd'
  140 |             scd(l);
      |             ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:141:13: note: in expansion of macro 'scd'
  141 |             scd(r);
      |             ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:142:13: note: in expansion of macro 'scd'
  142 |             scd(c);
      |             ^~~
foodcourt.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
foodcourt.cpp:143:13: note: in expansion of macro 'sclld'
  143 |             sclld(k);
      |             ^~~~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:149:13: note: in expansion of macro 'scd'
  149 |             scd(l);
      |             ^~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:150:13: note: in expansion of macro 'scd'
  150 |             scd(r);
      |             ^~~
foodcourt.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
foodcourt.cpp:151:13: note: in expansion of macro 'sclld'
  151 |             sclld(k);
      |             ^~~~~
foodcourt.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)
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:158:13: note: in expansion of macro 'scd'
  158 |             scd(a);
      |             ^~~
foodcourt.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
foodcourt.cpp:159:13: note: in expansion of macro 'sclld'
  159 |             sclld(b);
      |             ^~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 20812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 205 ms 30404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 10380 KB Output is correct
2 Correct 63 ms 10760 KB Output is correct
3 Correct 58 ms 11196 KB Output is correct
4 Correct 41 ms 8812 KB Output is correct
5 Correct 50 ms 10224 KB Output is correct
6 Correct 60 ms 11080 KB Output is correct
7 Correct 31 ms 7016 KB Output is correct
8 Correct 29 ms 6560 KB Output is correct
9 Correct 51 ms 10900 KB Output is correct
10 Correct 38 ms 8512 KB Output is correct
11 Correct 56 ms 11076 KB Output is correct
12 Correct 56 ms 10888 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -