Beams of Light

Solution by TioPatinhas — 100 pts

Code / Notes

#include <bits/stdc++.h>
using namespace std;

// Problema Atual: 6
int main() {
	int n, l, q;
    cin >> n >> l >> q;
    vector<int>V(n+2, 0);
    for (int i = 0; i < l; i++) {
        int Pi, Ri;
        cin >> Pi >> Ri;
        int l = max(0, Pi-Ri);
        int r = min(n, Pi+Ri);
        V[l]++;
        V[r+1]--;
/*
0 0 0 0 0 0 0 0 0 0
   [    X    ]
    1         -1
0 0 1 1 1 1 0 0 0 0
*/
    }
    int S = 0;
    for (int i = 0; i < n+1; i++) {
        S += V[i];
        V[i] = S;
    }
    for (int i = 0; i < q; i++) {
        int Ai;
        cin >> Ai;
        if (V[Ai] != 0) {
            cout << 'Y' << endl;
        }
        else {
            cout << 'N' << endl;
        }
    }
}

/*

Delta Encoding?
Soma de Prefixos?
      L              R
0 0 0 0 0 0 0 0 0 0  0 0 0  0 0
     [           ] +1
         [              ] +2
0 0 0 1 0 2 0 0 0 -1 0 0 -2 0 0
soma de prefixo:
0 0 0 1 1 3 3 3 3  2 2 2  0 0 0

vector<int> A; // valores
vector<int> P;
P[0] = A[0];
for (int i = 1; i < P.size(); i++) {
    P[i] = P[i-1] + A[i];
}
*/

Last updated 13 hours, 55 minutes ago

« Back to problem