oj.uz

Submission #48399

# Submission time Handle Problem Language Result Execution time Memory
48399 2018-05-12T17:36:20 Z ernestvw Weighting stones (IZhO11_stones) C++11
0 / 100
 97 ms 5244 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int nbStones;
int MINI[300000];
int MAXI[300000];
int lazy[300000];

const int oo = 1e9;

void update(int l, int r, int L, int R, int n, int val){
    if(lazy[n]){
        MINI[n]+=lazy[n];
        MAXI[n]+=lazy[n];
        lazy[2*n+1]+=lazy[n];
        lazy[2*n+2]+=lazy[n];
        lazy[n]=0;
    }
    if(l>r or R<l or L>r)return;
    if(L <= l and r <= R){
        lazy[2*n+1]+=val;
        lazy[2*n+2]+=val;
        MAXI[n]+=val;
        MINI[n]+=val;
        return;
    }
    update(l, (l+r)/2, L, R, 2*n+1, val);
    update((l+r)/2+1, r, L, R, 2*n+2, val);
    MINI[n]=min(MINI[2*n+1], MINI[2*n+2]);
    MAXI[n]=max(MAXI[2*n+1], MAXI[2*n+2]);
}

int MIN(){
    if(lazy[0]){
        lazy[1]+=lazy[0];
        lazy[2]+=lazy[0];
        MINI[0]+=lazy[0];
        MAXI[0]+=lazy[0];
        lazy[0]=0;
    }
    return MINI[0];
}

int MAX(){
    if(lazy[0]){
        lazy[1]+=lazy[0];
        lazy[2]+=lazy[0];
        MINI[0]+=lazy[0];
        MAXI[0]+=lazy[0];
        lazy[0]=0;
    }
    return MAXI[0];
}

int main(){
    scanf("%d", &nbStones);
    fill_n(MINI, 300000, 0);
    fill_n(MAXI, 300000, 0);
    int maxi = 0;
    int mini = 0;
    for(int q = 1; q <= nbStones; q++){
        int indice, side;
        scanf("%d%d", &indice, &side);
        /*for(int i = 1; i <= nbStones; i++)
            if(i <= indice)
                suffix[i]+=(side==1?1:-1);
        maxi=0,mini=0;
        for(int i=1;i<=nbStones;i++)
            maxi=max(maxi, suffix[i]), mini=min(mini, suffix[i]);*/
        update(0, nbStones, 1, indice, 0, (side==1?1:-1));
        maxi=MAX();
        mini=MIN();
        if(maxi>0 and mini<0)printf("?");
        else if(maxi==0 and mini==0)printf("?");
        else if(maxi>0)printf(">");
        else if(mini<0)printf("<");
        printf("\n");
    }
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbStones);
     ~~~~~^~~~~~~~~~~~~~~~~
stones.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &indice, &side);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 4 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2820 KB Output is correct
6 Correct 4 ms 2820 KB Output is correct
7 Correct 4 ms 2880 KB Output is correct
8 Correct 5 ms 2896 KB Output is correct
9 Correct 4 ms 2896 KB Output is correct
10 Correct 10 ms 3196 KB Output is correct
11 Correct 58 ms 4220 KB Output is correct
12 Incorrect 97 ms 5244 KB Output isn't correct
13 Halted 0 ms 0 KB -