Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2018 Zemljiški kataster C++ 0/100Napaka med izvajanjem / ob izhodu (RTE) 13. okt '18 @ 15:38

Test Točke Porabljen spomin Porabljen čas Status
#1 0/10 2,898 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#2 0/10 3,332 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​-1
-1
-1
-1
6
Pravilen izhod:
​17
64
64
7
32
#3 0/10 3,336 MiB 0,010 s Napačen odgovor
Tvoj izhod:
​-1
-1
-1
35
-1
Pravilen izhod:
​288
278
158
134
20
#4 0/10 3,316 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​70
-1
-1
-1
-1
Pravilen izhod:
​929
429
309
20
130
#5 0/10 6,719 MiB 0,056 s Napačen odgovor
Tvoj izhod:
​-1
-1
-1
-1
-1
Pravilen izhod:
​5887
5714
408
6145
4016
#6 0/10 7,316 MiB 0,209 s Napaka med izvajanjem / ob izhodu
#7 0/10 14,461 MiB 0,268 s Napaka med izvajanjem / ob izhodu
#8 0/10 10,813 MiB 0,184 s Napaka med izvajanjem / ob izhodu
#9 0/10 11,148 MiB 0,527 s Napaka med izvajanjem / ob izhodu
#10 0/10 12,297 MiB 0,263 s Napaka med izvajanjem / ob izhodu

Ocenjevani program (ZemljiskiKataster.cpp):
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define INF (1LL << 55)
#define maxn 1111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

struct node{
    int val, lft, rgt;    
};

int arr[111][maxn];

vector<vector<int> > v[maxn];
node seg[4 * maxn];

node combine(node a, node b){
    if(a.val == -1)
        return b;
    if(b.val == -1)
        return a;
    
    
    node ret;
    ret.val = a.val + b.val;
    ret.lft = a.lft;
    ret.rgt = b.rgt;
        
    int ind = 0;
    for(int i = 0; i < v[a.rgt].size(); i++){
        int vred = v[a.rgt][i][0];
        int leva = v[a.rgt][i][1];
        int desna = v[a.rgt][i][2];
        
        while(ind >= 0 && ind < v[b.lft][ind].size() && v[b.lft][ind][1] <= desna){
            if(v[b.lft][ind][0] == vred && max(leva, v[b.lft][ind][1]) <= min(desna, v[b.lft][ind][1]))
                ret.val--;
            
            ind++;
        }
        ind--;
    }
    
    return ret;
}


void build(int x, int l, int d){
    if(l > d)
        return;
    
    if(l == d){
        seg[x].val = v[l].size();
        seg[x].lft = seg[x].rgt = l;
        return;
    }
    
    int mid = (l + d) / 2;
    build(2 * x, l, mid);
    build(2 * x + 1, mid +1 , d);
    seg[x] = combine(seg[2 * x], seg[2 * x + 1]);
}

node query(int x, int l, int d, int i, int j){
    if(l > d || l > j || i > d)
        return {-1, -1, -1};
    
    if(i <= l && d <= j)
        return seg[x];
    
    int mid = (l + d) / 2;
    node leva = query(2 * x, l, mid, i, j);
    node desna = query(2 * x + 1, mid +1 , d, i, j);
    return combine(leva, desna);
}



int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            scanf("%d", arr[i] + j);
    }
    
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            int zac = j;
            while(zac <= n && arr[zac][i] == arr[j][i])
                zac++;
            
            v[i].pb({arr[j][i], j, zac - 1});
            j = zac - 1;
        }
    }

    
    
    build(1, 1, n);
    
    int q;
    scanf("%d", &q);
    while(q--){
        int a, b;
        scanf("%d%d", &a, &b);
       printf("%d\n", query(1, 1, n, a, b).val);
    }
    
	return 0;
}