oj.uz

답안 #589330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589330 2022-07-04T13:11:47 Z FatihSolak 휴가 (IOI14_holiday) C++17
100 / 100
 211 ms 7612 KB 
#include <bits/stdc++.h>
#define N 100005
#include"holiday.h"
using namespace std;
struct BIT{
    vector<long long> bit;
    int n;
    BIT(int size){
        n = size;
        bit.assign(n,0);
    }
    void upd(int pos,int val){
        for(;pos < n;pos += pos & -pos){
            bit[pos] += val;
        }
    }
    long long get(int pos){
        long long ret = 0;
        for(;pos > 0;pos -= pos & -pos){
            ret += bit[pos];
        }
        return ret;
    }
    int get_kth(int k){
        int ret = 0;
        for(int i = 20;i>=0;i--){
            if((1<<i) + ret < n && bit[ret + (1<<i)] < k){
                k -= bit[ret + (1<<i)];
                ret += (1<<i);
            }
        }
        return ret+1;
    }
};
int rel[N];
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ans = 0;
    vector<int> compress;
    for(int i = 0;i<n;i++){
        compress.push_back(-attraction[i]);
    }
    sort(compress.begin(),compress.end());
    compress.resize(unique(compress.begin(),compress.end())-compress.begin());
    for(int i = 0;i<compress.size();i++){
        rel[i+1] = -compress[i];
    }
    for(int i = 0;i<n;i++){
        attraction[i] = lower_bound(compress.begin(),compress.end(),-attraction[i])-compress.begin() + 1;
    }
    vector<pair<pair<int,int>,pair<int,int>>> q;
    q.push_back({{0,start},{start,n-1}});
    while(q.size()){
        vector<pair<pair<int,int>,pair<int,int>>> nw;
        BIT bt1(n);
        BIT bt2(n);
        int l = 0,r = -1;
        for(auto u:q){
            //cout << u.first.first << " " << u.first.second << endl;
            //cout << u.second.first << " " << u.second.second << endl;
            if(u.first.first > u.first.second)continue;
            int m = (u.first.first + u.first.second)/2;
            while(l < m){
                bt1.upd(attraction[l],-1);
                bt2.upd(attraction[l],-rel[attraction[l]]);
                l++;
            }
            int opt = u.second.first;
            long long maxi = 0;
            for(int i = u.second.first;i<=u.second.second;i++){
                while(r < i){
                    r++;
                    bt1.upd(attraction[r],1);
                    bt2.upd(attraction[r],rel[attraction[r]]);
                }
                //cout << l << " " << m << " " << r << " " << i << endl;
                int cost = 0;
                if(m == start || i == start)cost = abs(m-start)+abs(i-start);
                else cost = abs(m-i)+min(abs(m-start),abs(i-start));
                int left = min(i-m+1,d - cost);
                if(left <= 0)continue;
                int pos = bt1.get_kth(left) -1;
                long long nowans = bt2.get(pos) + (left -  bt1.get(pos)) * (rel[pos+1]);
                //cout << cost << " " << left << " " << nowans << endl;
                if(nowans > maxi){
                    maxi = nowans;
                    opt = i;
                }
                ans = max(ans,nowans);
            }
            //cout << opt << endl;
            nw.push_back({{u.first.first,m-1},{u.second.first,opt}});
            nw.push_back({{m+1,u.first.second},{opt,u.second.second}});
        }
        q = nw;
    }
    return ans;
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0;i<compress.size();i++){
      |                   ~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2904 KB Output is correct
2 Correct 20 ms 2924 KB Output is correct
3 Correct 22 ms 2928 KB Output is correct
4 Correct 23 ms 2892 KB Output is correct
5 Correct 24 ms 2876 KB Output is correct
6 Correct 8 ms 1364 KB Output is correct
7 Correct 12 ms 1856 KB Output is correct
8 Correct 17 ms 2216 KB Output is correct
9 Correct 6 ms 1236 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 856 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 4 ms 836 KB Output is correct
6 Correct 1 ms 704 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 7612 KB Output is correct
2 Correct 26 ms 4044 KB Output is correct
3 Correct 65 ms 3936 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 211 ms 5792 KB Output is correct
9 Correct 192 ms 5792 KB Output is correct