oj.uz

답안 #799246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799246 2023-07-31T11:09:17 Z bane Watering can (POI13_kon) C++17
90 / 100
 3868 ms 131072 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <string.h>
#include <bitset>
#include <numeric>
#include <utility>
#include<math.h>
using namespace std;
#define ll long long
const int nax = 300'001;
int sq = 1400;
ll N, K, t[nax], zers[nax], ans[nax];
 
int mapa[216][300001];
 
void inicjuj(int n, int k, int *D)
{
    //sq = min(550, (int)sqrt(n) + 1);
    for (int i = 0; i < n; i++){
        t[i] = D[i];
    }
    N = n, K = k;
    for (int i = 0; i < n; i++){
        if (K >= t[i] && K - t[i] <= 300000)
            mapa[i / sq][-(K - t[i]) + 300000]++;
        if (t[i] >= K)ans[i / sq]++;
    }
    
}
 
void podlej(int a, int b)
{
    //--a,--b;
    int from = a/sq, to = (b / sq);
    for (int i = from; i <= to; i++){
        if (a <= i * sq && b >= (i + 1) * sq - 1){
            zers[i]++;
            ans[i] += mapa[i][300000 - zers[i]];
        }else{
            ans[i] = 0;
            for (int j = i * sq; j / sq == i && j < N; j++){
                if (K >= t[j] && K - t[j] <= 300000)
                    mapa[i][-(K - t[j]) + 300000]--;
                t[j] += zers[i];
                if (j >= a && j <= b)t[j]++;
                if (K >= t[j] && K - t[j] <= 300000){
                    mapa[i][- (K - t[j]) + 300000]++;
                }
                if (t[j] >= K)ans[i]++;
            }
            zers[i] = 0;
            
        }
    }
}
 
int dojrzale(int a, int b)
{
   // --a,--b;
    int odg = 0;
    int from = a/sq, to = (b / sq);
    for (int i = from; i <= to; i++){
        if (a <= i * sq && b >= (i + 1) * sq - 1){
            odg += ans[i];
        }else{
            for (int j = max(a, i * sq); j / sq == i && j <= b; j++){
                odg += (t[j] + zers[i] >= K);
            }   
        }
    }
    return odg;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1492 KB Output is correct
2 Correct 17 ms 1640 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 2660 KB Output is correct
2 Correct 485 ms 2768 KB Output is correct
3 Correct 379 ms 2700 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 690 ms 3396 KB Output is correct
2 Correct 842 ms 4516 KB Output is correct
3 Correct 690 ms 2944 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1264 ms 75744 KB Output is correct
2 Correct 902 ms 58076 KB Output is correct
3 Correct 925 ms 3284 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3173 ms 105084 KB Output is correct
2 Correct 1827 ms 67736 KB Output is correct
3 Correct 2089 ms 3540 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2332 ms 98280 KB Output is correct
2 Correct 2005 ms 118680 KB Output is correct
3 Correct 1873 ms 4932 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 765 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3232 ms 20220 KB Output is correct
2 Correct 2545 ms 12580 KB Output is correct
3 Correct 3181 ms 10288 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3332 ms 18836 KB Output is correct
2 Correct 2935 ms 16680 KB Output is correct
3 Correct 3868 ms 6592 KB Output is correct