~3 CCF 2022-03-2 travel plan

Title Description

Input

Output

The sample input

6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2

Sample output

3
3

Source code

70 branch reason ： error

#include <iostream>

using namespace  std;


int main (){
    
    int n,m,k;
    cin>>n>>m>>k;
    int temp=0;
    int result=0;
    int *arrTime = new int [n];
    int *arrLimit = new int [n];
    int *sign= new int[m];
    bool ssi= true;
    for (int i = 0; i <n ; i++) {
    
        int g,h;
        cin>>g>>h;
        arrTime[i]=g;
        arrLimit[i]=h;
    }
    for (int i = 0; i < m; i++) {
    
        cin>>temp;
        ssi=true;
        int low, high, mid;
        low = 0;
        high =n - 1;
        while (low <= high) {
    
            mid = (low + high) / 2;
            if (arrTime[mid] < temp+k)
                low = mid + 1;
            else if (arrTime[mid] >temp+k)
                high = mid - 1;
            else{
    
                sign[i]= mid;
                ssi= false;
                break;
            }
        }
        if (ssi){
    
            sign[i]= mid;
        }
        for (int j = sign[i]; j <n ; j++) {
    
            if (arrTime[j] >= temp+k ){
    
                if (arrTime[j]<=temp+k+arrLimit[j]-1){
    
                    result++;
                }
            }
        }
        cout<<result<<endl;
        result=0;
    }

    return 0;
}

100 branch ：

#include <iostream>
#include <vector>
using namespace  std;


int main (){
    
    int n, m, k;
    cin >> n >> m >> k;
    int l, r;
    vector<int> v(200010);
    for (int i = 0; i < n; i++) {
    
        cin >> l >> r;
        int tl = max(0, l - r - k + 1);
        int tr = max(0, l - k);
        v[tl]++;
        v[tr + 1]--;
    }
    for (int i = 1; i < 200010; i++) {
    
        v[i] += v[i - 1];
    }
    for (int i = 0; i < m; i++) {
    
        cin >> l;
        cout << v[l] << endl;
    }

    return 0;

}

About this problem

For the first time Although there was no timeout But still 70 branch
I saw others' solutions later , Find that you can change your mind , We get the number of places where nucleic acids can enter at each time point , You don't need two for Loop through , Here we use the differential array .

Difference array
A differential array is a data structure . Equivalent to the inverse operation of prefix sum .
The function of the difference array is to modify the interval , Query point .
The time complexity of modifying the interval is O(1).
The time complexity of the query point is O(n). If combined with tree array, the time complexity can reach O(log n).
（1） The values of the elements in the array are all 0

Original array ： 0 0 0 0 0 0
Subscript ： 0 1 2 3 4 5
Now we need to subscript 2-4 Add the number between 5

Modification interval ：
Difference array ： 0 0 5 0 0 -5
Subscript ： 0 1 2 3 4 5

result ：
Result array ： 0 0 5 5 5 0
Subscript ： 0 1 2 3 4 5

Modification interval ： Subscript to be x-y Add the number between n
Mark the subscript as x Sum of numbers n, Subscript to be y The number of minus n
Get the modified result array ： The first number of the result array is the same as the first number of the difference array , Each number of the subsequent result array is equal to the current number of the difference group minus the previous number of the difference array .

（2） Other situations

Original array ： 4 7 9 6 5 2
Subscript ： 0 1 2 3 4 5
Now we need to subscript 1-2 Add the number between 3

First get the difference array ：
Difference array ： 4 3 2 -3 -1 -3
Subscript ： 0 1 2 3 4 5

Modification interval ：
Difference array ： 4 6 2 -6 -1 -3
Subscript ： 0 1 2 3 4 5

result ：
Result array ： 4 10 12 6 5 2
Subscript ： 0 1 2 3 4 5

Get the difference array ： The first number is consistent with the original array , Each subsequent number is equal to the current number of the original array minus the previous number of the current number of the original array
Modification interval ： Subscript to be x-y Add the number between n
Mark the subscript as x Sum of numbers n, Subscript to be y The number of minus n
Get the modified result array ： The first number of the result array is the same as the first number of the difference array , Each number of the subsequent result array is equal to the current number of the difference group minus the previous number of the current number of the difference array .