oj.uz

답안 #818142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
818142 2023-08-10T02:46:27 Z 1075508020060209tc Meteors (POI11_met) C++14
74 / 100
 1044 ms 39392 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int lowbit(int x){return x&-x;}
int bit[500005];
void upd(int pl,int v){
while(pl){
    bit[pl]+=v;
    pl-=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl<=500000){
    ret+=bit[pl];
    pl+=lowbit(pl);
}
return ret;
}
int m;int n;
vector<int>own[500005];
int tgt[500005];
int lar[500005];
int rar[500005];
int opad[500005];
int Q;
int ans[500005];

void doop(int l,int r){
for(int i=l;i<=r;i++){
    if(lar[i]<=rar[i]){
        upd(rar[i],opad[i]);
        upd(lar[i]-1,-opad[i]);
    }else{
        upd(rar[i],opad[i]);
        upd(n,opad[i]);
        upd(lar[i]-1,-opad[i]);
    }
}
}
void undo(int l,int r){
for(int i=l;i<=r;i++){
    if(lar[i]<=rar[i]){
        upd(rar[i],-opad[i]);
        upd(lar[i]-1,opad[i]);
    }else{
        upd(rar[i],-opad[i]);
        upd(n,-opad[i]);
        upd(lar[i]-1,opad[i]);
    }
}
}


void solve(int l,int r,vector<int>qid){
if(l==r){
    for(int i=0;i<qid.size();i++){
        ans[qid[i]]=l;
    }

    return;
}
int mi=(l+r)/2;
doop(l,mi);
vector<int>qa;vector<int>qb;
for(int i=0;i<qid.size();i++){
    int id=qid[i];
    int cal=0;
    for(int j=0;j<own[id].size();j++){
        int pl=own[id][j];
        cal+=qsum(pl);
    }
    if(cal>=tgt[id]){
        qa.push_back(id);
    }else{
        qb.push_back(id);
    }
}
vector<int>().swap(qid);
solve(mi+1,r,qb);
undo(l,mi);
solve(l,mi,qa);
}






signed main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
    int v;
    cin>>v;
    own[v].push_back(i);
}
for(int i=1;i<=m;i++){
    cin>>tgt[i];
}
cin>>Q;
for(int i=1;i<=Q;i++){
    cin>>lar[i]>>rar[i]>>opad[i];
}
lar[Q+1]=1;
rar[Q+1]=1;
opad[Q+1]=0;
vector<int>vc;
for(int i=1;i<=m;i++){
    vc.push_back(i);
}
solve(1,Q+1,vc);
for(int i=1;i<=m;i++){
    if(ans[i]==Q+1){
        cout<<"NIE\n";
    }else{
        cout<<ans[i]<<"\n";
    }
}


}

Compilation message

met.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>)':
met.cpp:59:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<qid.size();i++){
      |                 ~^~~~~~~~~~~
met.cpp:68:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 | for(int i=0;i<qid.size();i++){
      |             ~^~~~~~~~~~~
met.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<own[id].size();j++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 9 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 12224 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 15052 KB Output is correct
2 Correct 109 ms 18464 KB Output is correct
3 Correct 99 ms 15096 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 14808 KB Output is correct
2 Correct 97 ms 14848 KB Output is correct
3 Correct 114 ms 17016 KB Output is correct
4 Correct 40 ms 14708 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 14680 KB Output is correct
2 Correct 87 ms 17224 KB Output is correct
3 Correct 47 ms 13268 KB Output is correct
4 Correct 99 ms 15288 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 14152 KB Output is correct
2 Correct 98 ms 14912 KB Output is correct
3 Correct 94 ms 14496 KB Output is correct
4 Correct 121 ms 16348 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1044 ms 39392 KB Output is correct
2 Incorrect 515 ms 23960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 960 ms 35832 KB Output is correct
2 Incorrect 353 ms 23960 KB Output isn't correct
3 Halted 0 ms 0 KB -