oj.uz

답안 #461201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
461201 2021-08-09T13:54:31 Z idas Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 19740 KB 
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define SZ(x) ((int)((x).size()))
#define LE(vec) vec[vec.size()-1]
#define TSTS int t; cin >> t; while(t--)solve()

const int INF = 1e9;
const long long LINF = 1e18;
const long double PI = asin(1)*2;
const int MOD = 1e9+7;

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;
typedef long double ld;

void setIO()
{
    FAST_IO;
}

void setIO (string s) {
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
 	freopen((s+".out").c_str(),"w",stdout);
}

const int N=1e5+10, L=17;

int n, q, a[N], d[N], par[N][L], sm[N][L];
bool v[N];

void pre(int i)
{
    v[i]=true;
    int lst=i, dl=d[i];
    FOR(j, i+1, n)
    {
        if(d[j]>dl){
            v[j]=true;
            par[lst][0]=j;
            sm[lst][0]=a[j];
            lst=j;
            dl=d[j];
        }
    }
}

void build()
{
    FOR(i, 1, L)
    {
        FOR(j, 0, n+1)
        {
            par[j][i]=par[par[j][i-1]][i-1];
            sm[j][i]=sm[j][i-1]+sm[par[j][i-1]][i-1];
        }
    }
}

int main()
{
    setIO();
    cin >> n >> q;
    FOR(i, 0, n)
    {
        cin >> d[i] >> a[i];
    }

    FOR(i, 0, n+1) par[i][0]=n;

    FOR(i, 0, n)
    {
        if(!v[i]){
            pre(i);
        }
    }
    build();
    FOR(i, 0, n+1)
    {
        FOR(j, 0, L)
        {
            if(par[i][j]==n){
                sm[i][j]=INF;
            }
        }
    }

    FOR(i, 0, q)
    {
        int p, x;
        cin >> p >> x;
        p--;
        int tot=a[p];
        if(tot>=x){
            cout << p+1 << '\n';
            continue;
        }
        bool going=true;
        while(going){
            going=false;
            for(int j=L-1; j>=0; j--){
                if(sm[p][j]+tot<x){
                    tot+=sm[p][j];
                    p=par[p][j];
                    going=true;
                }
            }
        }

        p=par[p][0];

        cout << (p==n?0:p+1) << '\n';
    }
}

Compilation message

fountain.cpp: In function 'void setIO(std::string)':
fountain.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 14456 KB Output is correct
2 Correct 211 ms 13524 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 204 ms 14456 KB Output is correct
9 Correct 211 ms 13524 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1482 ms 8684 KB Output is correct
12 Correct 317 ms 19740 KB Output is correct
13 Execution timed out 1596 ms 12984 KB Time limit exceeded
14 Halted 0 ms 0 KB -