oj.uz

답안 #556892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556892 2022-05-04T10:11:37 Z shahriarkhan Meteors (POI11_met) C++14
74 / 100
 833 ms 34640 KB 
#include<bits/stdc++.h>
using namespace std ;

const int MX = 3e5 + 5 ;

const long long INF = 1e18 + 5 ;

struct query
{
    int l = 0 , r = 0 ;
    long long val = 0 ;
};

struct BIT
{
    int n ;
    vector<long long> bit ;
    void init(int _n)
    {
        n = _n ;
        bit = vector<long long>(n+5,0) ;
    }
    int low_bit(int idx)
    {
        return idx&(-idx) ;
    }
    void add(int idx , long long val)
    {
        for(; idx <= n ; idx += low_bit(idx))
        {
            bit[idx] += val ;
        }
    }
    void update(int l , int r , long long val)
    {
        add(r + 1 , -val) , add(l , val) ;
        if(l>r) add(1,val) , add(n+1,-val) ;
    }
    long long query(int idx)
    {
        long long ret = 0 ;
        for(; idx > 0 ; idx -= low_bit(idx))
        {
            ret += bit[idx] ;
        }
        return ret ;
    }
} B ;

int n , m , k , o[MX] , ans[MX] ;

long long p[MX] ;

vector<int> owner[MX] ;

vector<query> q ;

void palbs(int low , int high , vector<int> &vals)
{
    if(low==high)
    {
        for(int &i : vals)
        {
            ans[i] = low ;
        }
        return ;
    }
    int mid = (low+high)>>1 ;
    for(int i = low ; i <= mid ; ++i)
    {
        B.update(q[i].l,q[i].r,q[i].val) ;
    }
    vector<int> ok , not_ok ;
    for(int c : vals)
    {
        long long sum = 0 ;
        for(int land : owner[c])
        {
           sum += B.query(land) ;
        }
        if(sum>=p[c]) ok.push_back(c) ;
        else
        {
            p[c] -= sum ;
            not_ok.push_back(c) ;
        }
    }
    for(int i = low ; i <= mid ; ++i)
    {
        B.update(q[i].l,q[i].r,-q[i].val) ;
    }
    palbs(low,mid,ok) ;
    palbs(mid+1,high,not_ok) ;
}

int main()
{
    vector<int> v ;
    scanf("%d%d",&n,&m) ;
    B.init(m+2) ;
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d",&o[i]) ;
        owner[o[i]].push_back(i) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%lld",&p[i]) ;
        ans[i] = -1 ;
        v.push_back(i) ;
    }
    scanf("%d",&k) ;
    for(int i = 1 ; i <= k ; ++i)
    {
        int l , r ;
        long long a ;
        scanf("%d%d%lld",&l,&r,&a) ;
        q.push_back({l,r,a}) ;
    }
    q.push_back({1,m,INF}) ;
    palbs(0,k,v) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(ans[i]!=k) printf("%d\n",ans[i]+1) ;
        else puts("NIE") ;
    }
    return 0 ;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d",&n,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~
met.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d",&o[i]) ;
      |         ~~~~~^~~~~~~~~~~~
met.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%lld",&p[i]) ;
      |         ~~~~~^~~~~~~~~~~~~~
met.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d",&k) ;
      |     ~~~~~^~~~~~~~~
met.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf("%d%d%lld",&l,&r,&a) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7448 KB Output is correct
3 Correct 5 ms 7368 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7364 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7364 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 10316 KB Output is correct
2 Correct 95 ms 12552 KB Output is correct
3 Correct 79 ms 10764 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 10740 KB Output is correct
2 Correct 88 ms 10760 KB Output is correct
3 Correct 95 ms 11992 KB Output is correct
4 Correct 30 ms 9760 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 10308 KB Output is correct
2 Correct 80 ms 12140 KB Output is correct
3 Correct 43 ms 9036 KB Output is correct
4 Correct 83 ms 11068 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 10184 KB Output is correct
2 Correct 86 ms 10808 KB Output is correct
3 Correct 69 ms 10436 KB Output is correct
4 Correct 97 ms 11876 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 833 ms 34640 KB Output is correct
2 Incorrect 630 ms 27452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 781 ms 32368 KB Output is correct
2 Incorrect 654 ms 26104 KB Output isn't correct
3 Halted 0 ms 0 KB -