oj.uz

답안 #944133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944133 2024-03-12T08:51:54 Z Warinchai Meteors (POI11_met) C++14
74 / 100
 1470 ms 65536 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int own[350005];
vector<int>states[350005];
int least[350005];
struct fenwick{
    int info[350005];
    void upd(int x,int val){
        for(int i=x;i<=350001;i+=i&-i)info[i]+=val;
    }
    int fval(int x){
        int sum=0;
        for(int i=x;i>0;i-=i&-i)sum+=info[i];
        return sum;
    }
    void clear(){
        for(int i=1;i<=350001;i++)info[i]=0;
    }
}tr;
int st[350005];
int en[350005];
struct meteor{
    int l,r,a;
    meteor(int x,int y,int z){
        l=x,r=y,a=z;
    }
};
vector<meteor>events;
vector<int>query[350005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>own[i];
        states[own[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>least[i];
    }
    int k;cin>>k;
    int a,b,c,md,cur,l,r,sum,x;
    for(int i=1;i<=k;i++){
        a,b,c;cin>>a>>b>>c;
        events.push_back(meteor(a,b,c));
    }
    for(int i=1;i<=n;i++){
        st[i]=1;en[i]=k+1;
        md=(st[i]+en[i])/2;
        query[md].push_back(i);
    }
    //cout<<"work\n";
    while(1){
        cur=0;
        for(auto x:events){
            cur++;
            //cout<<"EVENT:"<<cur<<"\n";
            l=x.l;
            r=x.r;
            if(l<=r)tr.upd(l,x.a),tr.upd(r+1,x.a*-1);
            else tr.upd(l,x.a),tr.upd(m+1,x.a*-1),tr.upd(1,x.a),tr.upd(r+1,x.a*-1);
            for(auto y:query[cur]){
                //cerr<<"STATE:"<<y<<"\n";
                sum=0;
                for(auto z:states[y]){
                    //cerr<<"STATION:"<<z<<" "<<tr.fval(1,m,1,z)<<"\n";
                    sum+=tr.fval(z);
                    if(sum>=least[y])break;
                }
                if(sum>=least[y]){
                    //cerr<<"ENOUGH\n";
                    en[y]=cur;
                }else{
                    //cerr<<"NOT ENOUGH\n";
                    st[y]=cur+1;
                }
            }
            query[cur].clear();
        }
        tr.clear();
        int check=1;
        for(int i=1;i<=n;i++){
            if(st[i]!=en[i]){
                check=0;
                md=(st[i]+en[i])/2;
                query[md].push_back(i);
            }
        }
        if(check)break;
    }
    for(int i=1;i<=n;i++){
        x=st[i];
        if(x==k+1)cout<<"NIE\n";
        else cout<<x<<"\n";
    }
}

Compilation message

met.cpp: In function 'int32_t main()':
met.cpp:45:9: warning: left operand of comma operator has no effect [-Wunused-value]
   45 |         a,b,c;cin>>a>>b>>c;
      |         ^
met.cpp:45:13: warning: right operand of comma operator has no effect [-Wunused-value]
   45 |         a,b,c;cin>>a>>b>>c;
      |             ^
met.cpp:45:14: warning: right operand of comma operator has no effect [-Wunused-value]
   45 |         a,b,c;cin>>a>>b>>c;
      |              ^

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 27596 KB Output is correct
2 Correct 151 ms 34692 KB Output is correct
3 Correct 92 ms 29640 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 28872 KB Output is correct
2 Correct 107 ms 29100 KB Output is correct
3 Correct 173 ms 35012 KB Output is correct
4 Correct 26 ms 27936 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 28192 KB Output is correct
2 Correct 117 ms 34932 KB Output is correct
3 Correct 109 ms 26572 KB Output is correct
4 Correct 99 ms 30268 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 27052 KB Output is correct
2 Correct 143 ms 28804 KB Output is correct
3 Correct 75 ms 27328 KB Output is correct
4 Correct 130 ms 36200 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1031 ms 59520 KB Output is correct
2 Correct 1470 ms 37456 KB Output is correct
3 Correct 591 ms 33576 KB Output is correct
4 Runtime error 983 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1184 ms 58588 KB Output is correct
2 Correct 671 ms 37968 KB Output is correct
3 Correct 476 ms 33416 KB Output is correct
4 Runtime error 979 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -