제출 #624527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624527		Stavab	Fountain (eJOI20_fountain)	C++14	100 / 100	396 ms	28220 KiB

fountain

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int depth;
vector<pair<int, int>> nums;
vector<int> segTree;
vector<vector<int>> parent, sumEdges;

void build(int v, int l, int r)
{
    if(l == r)
    {
        segTree[v] = nums[l].first; 
    }
    else
    {
        int m = (l + r) / 2;
        
        build(2*v, l, m);
        build(2*v + 1, m + 1, r);
        
        segTree[v] = max(segTree[2*v], segTree[2*v + 1]);
    }
}

void erase(int target, int v, int l, int r)
{
    if(l == r)
    {
        segTree[v] = 0;
    }
    else
    {
        int m = (l + r) / 2;
        
        if(target <= m)
            erase(target, 2*v, l, m);
        else
            erase(target, 2*v + 1, m + 1, r);
            
        segTree[v] = max(segTree[2*v], segTree[2*v + 1]);
    }
}

int findParent(int val, int v, int l, int r)
{
    if(l == r)
    {
        return l;
    }
    else
    {
        int m = (l + r) / 2;
        
        if(segTree[2*v] > val)
            return findParent(val, 2*v, l, m);
        else if(segTree[2*v + 1] > val)
            return findParent(val, 2*v + 1, m + 1, r);
        else
            return 0;
    }
}

void binaryUplifting()
{
    for(int i = 1; i < depth; i++)
    {
        for(int j = 0; j < parent.size(); j++)
        {
            if(parent[j][i - 1] == -1)
            {
                parent[j][i] = -1;
                continue;
            }
            
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
            
            if(parent[j][i] != -1)
                sumEdges[j][i] = sumEdges[j][i - 1] + sumEdges[parent[j][i - 1]][i - 1];
        }
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    nums.assign(n + 1, pair<int, int>());
    segTree.assign(4*n, 0);
    
    int d, c;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &d, &c);
        
        nums[i] = make_pair(d, c);
    }

    build(1, 1, n);

    depth = log2(n) + 2;
    parent.assign(n + 1, vector<int>(depth));
    sumEdges.assign(n + 1, vector<int>(depth));
    
    parent[0][0] = -1;
    sumEdges[0][0] = -1;
    for(int i = 1; i <= n; i++)
    {
        erase(i, 1, 1, n);
        
        parent[i][0] = findParent(nums[i].first, 1, 1, n);
        sumEdges[i][0] = nums[i].second;
    }

    binaryUplifting();
    
    int r, v;
    while(m--)
    {
        scanf("%d %d", &r, &v); 
        
        int curNode = r, curReach = depth - 1;
        while(curReach >= 0)
        {
            if(parent[curNode][curReach] == -1)
            {
                curReach--;
                continue;
            }
            
            if(sumEdges[curNode][curReach] < v)
            {
                v -= sumEdges[curNode][curReach];
                curNode = parent[curNode][curReach]; 
            }
            
            curReach--;
        }
        
        printf("%d\n", curNode);
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fountain.cpp: In function 'void binaryUplifting()':
fountain.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0; j < parent.size(); j++)
      |                        ~~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d %d", &d, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%d %d", &r, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40