Untitled

import java.util.ArrayList;
import java.util.HashMap;
 
class UserSolution
 
{
    int n = 0;
    int size;
    int sum[] = new int[500];
    int numberOfdes[] = new int[10000000];
    int numberOftype[] = new int[1000000];
    HashMap<Integer, ArrayList<object1>> hmtype;
 
    public class object1 {
        int id;
 
        public object1(int id) {
            this.id = id;
        }
    }
 
    // int group = -1;
 
    void init(int N, int M, int mType[], int mTime[]) {
        int group = -1;
        n = N - 1;
        size = 200;
 
        numberOfdes = mTime;
        numberOftype = mType;
 
        hmtype = new HashMap<Integer, ArrayList<object1>>();
        // int count=0;
 
        for (int i = 0; i < n; i++) {
 
            // for (int j = 0; j < M; j++) {
 
            ArrayList<object1> list = hmtype.get(mType[i]);
            if (list == null) {
                list = new ArrayList<UserSolution.object1>();
                hmtype.put(mType[i], list);
            }
            list.add(new object1(i));
            // }
            // cho nguoi vao nhom
            if (i % size == 0) {
                group++;
                sum[group] = 0;
            }
            sum[group] += numberOfdes[i];
        }
        for (int i = 0; i < M; i++) {
 
        }
 
    }
 
    void destroy() {
 
    }
 
    void update(int mID, int mNewTime) {
        // mID-=1;
        int oldvalue = numberOfdes[mID];
        int group = mID / size;
        // update sum
        numberOfdes[mID] = mNewTime;
        sum[group] += mNewTime - oldvalue;
 
    }
 
    int updateByType(int mTypeID, int mRatio256) {
        int ans = 0;
 
        ArrayList<object1> list = hmtype.get(mTypeID);
 
        if (list != null) {
            for (object1 b : list) {
                // int c = numberOfdes[b.id];
                int newValue = (int) (numberOfdes[b.id] * mRatio256 / 256);
                update(b.id, newValue);
                ans += newValue;
            }
        }
        // UpdateSumforGroup(n, numberOfdes);
        return ans;
    }
 
    int calculate(int mA, int mB) {
        // mA-=1;
        // mB-=1;
        int group = 0;
        int ans = 0;
      int start= Math.min(mA, mB);
      int end= Math.max(mA, mB);
 
            for (int i = start; i < end; i++) {
                if (i % size == 0 && i / size != end / size) {
                    ans += sum[i / size];
                    i += size - 1;
                } else
 
                    ans += numberOfdes[i];
 
            }
         
             
          
        return ans;
    }
}










There is a radio program that delivers energetic music and traffic information in the morning hours during the morning commute.

There is a radio session that informs the expected time it takes to arrive at a destination when listeners send their stories, the current location they are at, and their destination.

You are a staff member of the radio program.

 

The city consists of one-dimensional roads in a line format.

There are N points on a road and each point from the starting position of the road has a Point ID numbered from 0 to N-1 in order.

A section refers to the distance between each point and the adjacent point and has a Section ID numbered from 0 to N – 2 starting from the starting position of the road.

Each section has a Road Type ID from 0 to M – 1. 

 

[Fig.1] shows the formation of roads where N is 6.

The section between Point 0 and Point 1 and the section between Point 4 and Point 5 are roads of the same type.

Likewise, the section between Point 1 and Point 2 and the section between Point 3 and Point 4 are roads of the same type.

 


______________________________________ [Fig. 1]

The expected passage times of each section are updated in real time.

The expected passage times of each section are also updated depending on the type of road.

The expected passage times of each section in both directions are the same.

Given the departure and arrival points, you are required to write a program that calculates the expected time it takes to arrive at a destination.

 

Implement each required function by referring to the following API description.

※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.

 

The following is the description of API to be written in the User Code.

void init(int N, int M, int mType[], int mTime[])

This function is called in the beginning of each test case.

There are N points. There are N-1 sections and M road types of each section.

Point ID is numbered from 0 to N-1 in order starting from the starting position of the road.

Section ID is numbered from 0 to N-2 in order from the one closest to the starting position of the road.

N-1 road types of each section are given as mType[] in order from the one closest to the starting position of the road and have a value from 0 to M – 1.

The current expected passage times of each section are given as mTime[] in order from the one closest to the starting position of the road.

The number of sections of the same road type is 200 at most.

 

__Parameters

_____N : The number of points ( 10 ≤ N ≤ 100,000 )

_____M : The road type ( 1 ≤ M ≤ 1,000 )

_____mType : The road type of each section ( 0 ≤ mType[] ≤ M – 1 )

_____mTime : The expected passage times of each section ( 1 ≤ mTime[] ≤ 1,000 )

void destroy()

This function is called at the end of each test case.

Even if the function is left empty, this does not affect the grading.

void update(int mID, int mNewTime)

This function updates the expected passage time of Section mID to mNewTime.

 

__Parameters

_____mID : The Section ID ( 0 ≤ mID ≤ N – 2 )

_____mNewTime : The expected passage time ( 1 ≤ mNewTime ≤ 1,000 )

int updateByType(int mTypeID, int mRatio256)

This function updates the passage time of all roads of the sections whose road types are mTypeID to the ratio of mRatio256 to 256 and removes the decimals after the update. This function returns the sum of all the updated sections’ passage times.

For instance, let’s say that the passage time before the update was 500 in a certain section. If mRatio is given as 200, the updated passage time is calculated as 500 * 200 / 256 and when the decimals are removed, the end result will be 390.

The value to be returned does not exceed 2,000,000,000.

 

__Parameters

_____mTypeID : The Road Type ID ( 0 ≤ mTypeID[] ≤ M – 1 )

_____mRatio : The ratio to be updated ( 200 ≤ mRatio ≤ 300 )

__Results

_____The sum of all the updated sections’ passage times

int calculate(int mA, int mB)

This function returns the expected time it takes to move from Point mA to Point mB.

The value to be returned does not exceed 2,000,000,000.

mA ≠ mB is guaranteed.

 

__Parameters

_____mA, mB : The Point ID ( 0 ≤ mA, mB ≤ N – 1 )

__Results

_____The expected time it takes to move from Point mA to Point mB













#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
 
int Time[100005]; //time for every section
int segTree[400020]; //4*100005 time for range of sections
vector<int> typeSection[1001]; //store type with sectionID
int n;
 
void build(int ind, int lo, int hi) {
    if (lo == hi) {
        segTree[ind] = Time[lo];
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * ind + 1, lo, mid);
    build(2 * ind + 2, mid + 1, hi);
    segTree[ind] = segTree[2 * ind + 1] + segTree[2 * ind + 2];
}
 
void init(int N, int M, int mType[], int mTime[])
{
    n = N;
    for (int i = 0; i < N - 1; i++) {
        Time[i] = mTime[i];
        typeSection[mType[i]].push_back(i);
    }
    build(0, 0, n - 1);
}
 
void destroy()
{
    for (int i = 0; i < 1001; i++) {
        typeSection[i].clear();
    }
}
void pointUpdate(int node, int lo, int hi, int idx, int val) {
    if (lo == hi) {
        segTree[node] += val;
        return;
    }
    int mid = (lo + hi) / 2;
    if (idx <= mid && idx >= lo)
        pointUpdate(2 * node + 1, lo, mid, idx, val);
    else
        pointUpdate(2 * node + 2, mid + 1, hi, idx, val);
 
    segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    return;
}
void update(int mID, int mNewTime)
{
    int updateVal = mNewTime - Time[mID];
    Time[mID] = mNewTime;
    pointUpdate(0, 0, n - 1, mID, updateVal);
 
}
 
int updateByType(int mTypeID, int mRatio256)
{
    int ans = 0;
    vector<int> v = typeSection[mTypeID];
    for (int i = 0; i < v.size(); i++) {
        int newTime = (Time[v[i]] * mRatio256 )/ 256;
        int diff = newTime - Time[v[i]];
        Time[v[i]] += diff;
        ans += newTime;
        pointUpdate(0, 0, n - 1, v[i], diff);
    }
 
 
    return ans;
}
 
 
int query(int node, int lo, int hi, int left, int right) {
    if ( hi<left or lo>right) return 0;
    if (lo >= left && hi <= right) return segTree[node];
     
     
    int mid = lo +( hi-lo) / 2;
    int leftSum = query(2 * node + 1, lo, mid, left, right);
    int rightSum = query(2 * node + 2, mid + 1, hi, left, right);
    return  leftSum+rightSum;
}
 
int calculate(int mA, int mB)
{
    if (mA > mB) swap(mA, mB);
 
    return query(0,0,n-1,mA,mB-1);
}