oj.uz

답안 #555090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
555090 2022-04-30T07:12:08 Z myungwoo Meteors (POI11_met) C++17
100 / 100
 1921 ms 65536 KB 
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ull;
vector<int> sect[300001];
vector<vector<int> > cp;
ull goal[300001];
struct Day{
    int l,r; ull cnt;
    Day(){} Day(int l, int r, ull cnt):l(l),r(r),cnt(cnt){}
};
struct Fenwick{
    int s,e;
    vector<ull> tree, tadd;
    Fenwick(){} Fenwick(int n):s(1),e(n),tree(n+1,0ULL){}
    void clear() { tree.clear(); tree.resize(e+1,0ULL); }
    void rupdate(int left, int right, ull by) {
        inupdate(left, by);
        inupdate(right+1, -by);
    }
    void inupdate(int at, ull by) {
        for(int i=at; i<=e && i; i+=i&-i) tree[i]+=by;
    }
    ull query(int at) {
        ull ans=0ULL;
        for(int i=at; i>=1; i&=(i-1)) ans+=tree[i];
        return ans;
    }
};

vector<Day> day(1);
int l[300001], r[300001];
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        int x; scanf("%d",&x);
        sect[x].push_back(i);
    }
    Fenwick fen(m);
    for(int i=1; i<=n; i++) {
        scanf("%llu",&goal[i]);
    }
    int q; scanf("%d",&q);
    for(int i=1; i<=q; i++) {
        int l,r; ull cnt;
        scanf("%d%d%llu",&l,&r,&cnt);
        day.push_back(Day(l,r,cnt));
    }
    cp.resize(q+1, vector<int>());
    for(int i=1; i<=n; i++) l[i]=0, r[i]=q+1;
    while(true) {
        bool good=false;
        for(int i=1; i<=n; i++) {
            if(l[i]+1<r[i]) {
                cp[(l[i]+r[i])>>1].push_back(i);
                good=true;
            }
        }
        if(!good) break;

        int pi=1;
        for(int i=1; i<=q; i++) {
            //bring meteor shower!!
            if(!cp[i].size()) continue;
            for(int j=pi; j<=i; pi=++j) {
                if(day[j].l<=day[j].r) {
                    fen.rupdate(day[j].l,day[j].r,day[j].cnt);
                } else {
                    fen.rupdate(1,day[j].r,day[j].cnt);
                    fen.rupdate(day[j].l,m,day[j].cnt);
                }
            }

            for(int nara: cp[i]) {
                ull sum=0ULL;
                for(int k: sect[nara]) sum+=fen.query(k);
                int mid=(l[nara]+r[nara])>>1;
                if(sum>=goal[nara]) r[nara]=mid;
                else l[nara]=mid;
            }
            cp[i].clear();
        }
        fen.clear();
    }

    for(int i=1; i<=n; i++) {
        if(r[i]!=q+1) printf("%d\n", r[i]);
        else puts("NIE");
    }
    return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
met.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         int x; scanf("%d",&x);
      |                ~~~~~^~~~~~~~~
met.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%llu",&goal[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     int q; scanf("%d",&q);
      |            ~~~~~^~~~~~~~~
met.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d%llu",&l,&r,&cnt);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 10512 KB Output is correct
2 Correct 115 ms 12488 KB Output is correct
3 Correct 112 ms 12172 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 11684 KB Output is correct
2 Correct 104 ms 11612 KB Output is correct
3 Correct 129 ms 12672 KB Output is correct
4 Correct 34 ms 9724 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 10972 KB Output is correct
2 Correct 94 ms 13172 KB Output is correct
3 Correct 34 ms 9468 KB Output is correct
4 Correct 102 ms 12560 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 10000 KB Output is correct
2 Correct 99 ms 11560 KB Output is correct
3 Correct 81 ms 10304 KB Output is correct
4 Correct 122 ms 13856 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1012 ms 35360 KB Output is correct
2 Correct 261 ms 22808 KB Output is correct
3 Correct 178 ms 19644 KB Output is correct
4 Correct 1734 ms 63192 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 996 ms 34208 KB Output is correct
2 Correct 547 ms 22752 KB Output is correct
3 Correct 101 ms 18696 KB Output is correct
4 Correct 1921 ms 65536 KB Output is correct