cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2016 · EasyRange queries

Alternating Range Additions

National Olympiad — National round (2016 season)

Submission name: red.cpp

Solve in Editor →

Problem summary

An initially zero sequence receives K operations (L,R,C), adding C at L, subtracting C at L+1 and continuing alternately through R. Answer B point-value queries.

Input

K B, then K triples L R C, then B queried positions.

Output

One resulting value per queried position.

Constraints

1 ≤ K,B ≤ 1000; 1 ≤ L ≤ R ≤ 10^9; 1 ≤ queried position ≤ 10^9; 1 ≤ C ≤ 1000.

Worked example

Input and output for the worked example discussed below.

Input

2 6
5 12 5
2 9 4
4
5
9
2
12
11

Output

4
1
1
4
-5
5

Solution analysis

  1. There is no need to allocate the sequence up to one billion. Store the K short operation descriptions instead.
  2. For a queried position M, an operation contributes zero unless L≤M≤R. Inside the interval its contribution is +C when M−L is even, and −C when odd. Sum these independent contributions.
  3. For query 5 in the sample, operation [5,12] contributes +5 while [2,9] contributes −4, giving 1. At position 12 only the first operation applies, with odd offset 7, so the value is −5.

Why it works

The final value is the sum of all operation contributions, and interval membership and offset parity reproduce each operation exactly.

Complexity: O(KB) time and O(K) space. At most one million simple membership checks are needed.

Watch out. Parity is relative to L, not absolute position. Endpoints are inclusive. N is not supplied in the input and does not need to be reconstructed.

Commented C++17 solution

An independently written complete program with standard headers.

// The final value is the sum of all operation contributions, and interval membership and offset parity
// reproduce each operation exactly..
#include<iostream>
#include<vector>
using namespace std;
struct Operation{
    int left,right,amount;
};
int main(){
    int operations,queries;
    cin>>operations>>queries;
    vector<Operation>changes(operations);
    for(Operation&change:changes){
        cin>>change.left>>change.right>>change.amount;
    }
    while(queries--){
        int position;
        cin>>position;
        int answer=0;
        for(const Operation&change:changes){
            if(change.left<=position&&position<=change.right){
                answer+=(position-change.left)%2==0?change.amount:-change.amount;
            }
        }
        cout<<answer<<'\n';
    }
}

Source: Arena Olimpiici ↗