oj.uz

Submission #793737

# Submission time Handle Problem Language Result Execution time Memory
793737 2023-07-26T06:06:02 Z 반딧불(#10057) Triangle Collection (CCO23_day2problem3) C++17
0 / 25
 306 ms 388 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
ll arr[200002];
ll val[200002];

void solve(){
    set<int> st;
    ll ans = 0;
    for(int i=1; i<=n; i++){
        val[i] = arr[i];
        if(val[i]) st.insert(i);
    }
    for(int i=1; i<=n; i++){
        while(val[i] >= 2){
            if(st.empty() || *st.begin() >= 2*i ||
               (*st.begin() == i && val[i] == 2 && ((int)st.size() == 1 || *next(st.begin()) >= 2*i))) break;
            int x = i, y = *st.begin();
            if(y==i && val[i]==2) y = *next(st.begin());
            ll k;
            if(x==y) k = val[x] / 3;
            else k = min(val[x] / 2, val[y]);
            ans += k;
            val[x] -= k*2, val[y] -= k;
            if(!val[x]) st.erase(x);
            if(x!=y && !val[y]) st.erase(y);
        }
    }
    printf("%lld\n", ans);
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    while(q--){
        int x; ll v;
        scanf("%d %lld", &x, &v);
        arr[x] += v;
        solve();
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:38:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d %lld", &x, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 9 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 9 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 9 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -