제출 #980998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980998		salmon	Boat (APIO16_boat)	C++14	31 / 100	585 ms	524288 KiB

boat

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

int N;
pair<int,int> lst[510];
int a, b;
int mod = 1'000'000'007;
long long int st[510 * 4];
vector<pair<int,int>> num;

void build(int i, int s, int e){
    st[i] = 0;

    int m = (s + e)/2;

    if(s != e){
        build(i * 2, s, m);
        build(i * 2 + 1, m + 1, e);
    }
}

void update(int i, int s, int e, int in, int k){
    st[i] += k;
    st[i] %= mod;

    if(s == e) return;

    int m = (s + e)/2;

    if(in <= m){
        update(i * 2, s , m, in , k);
    }
    else{
        update(i * 2 + 1, m + 1, e, in, k);
    }
}

long long int query(int i, int s, int e, int S, int E){
    if(S <= s && e <= E) return st[i];

    int m = (s + e)/2;
    long long int V = 0;

    if(S <= m){
        V += query(i * 2, s , m, S, E);
    }
    if(m < E){
        V += query(i * 2 + 1, m + 1, e, S, E);
    }
    return V %= mod;
}


int main(){

    scanf(" %d",&N);

    for(int i = 1; i <= N; i++){
        scanf(" %d",&a);
        scanf(" %d",&b);

        lst[i] = {a,b};

        for(int j = a; j <= b; j++){
            num.push_back({j,i});
        }
    }

    sort(num.begin(),num.end());

    build(1, 0 , N);

    int it = 0;

    update(1,0,N,0,1);

    while(it < num.size()){
        vector<int> v = {num[it].second};
        int t = num[it].first;
        it++;

        while(it < num.size() && num[it].first == t){
            v.push_back(num[it].second);
            it++;
        }

        reverse(v.begin(),v.end());

        for(int j : v){
            update(1,0,N,j, query(1,0,N, 0, j - 1));
        }
    }

    printf("%d",query(1,0,N, 0, N) - 1);
}
/*
2
1 2
2 3
*/

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

boat.cpp: In function 'int main()':
boat.cpp:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while(it < num.size()){
      |           ~~~^~~~~~~~~~~~
boat.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while(it < num.size() && num[it].first == t){
      |               ~~~^~~~~~~~~~~~
boat.cpp:94:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   94 |     printf("%d",query(1,0,N, 0, N) - 1);
      |             ~^  ~~~~~~~~~~~~~~~~~~~~~~
      |              |                     |
      |              int                   long long int
      |             %lld
boat.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
boat.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~
boat.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf(" %d",&b);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42