답안 #79610 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79610	2018-10-15T06:03:21 Z	triplem5ds	Meteors (POI11_met)	C++14	74 / 100	4835 ms	66560 KB

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int N = 3e5+5;

int lo[N], hi[N];
int n, m, k;
int a[N];   ///Meteor States
int cap[N]; ///Cap for each meteor
int l[N], r[N], add[N];
int val[N];
/*
    If i parallel binary search how should i handle
    the L[i], R[i] updates with segment tree
*/
vector<int> corrsponds[N];
int ans[N];
vector<int> qu[2][N];
const int off = 512*1024;
ll laz[off<<1];
void upd(int l, int r,int v){
    l += off;
    r += off;
    laz[l]+=v;
    if(l!=r)laz[r]+=v;
    while(l+1<r){
        if(l&1^1)laz[l+1]+=v;
        if(r&1)laz[r-1]+=v;
        l >>= 1;
        r >>= 1;
    }
}
ll qry(int idx){
    ll ret = 0;idx++;
    for(int i = off+idx;i>=1;i>>=1)
        ret += laz[i];
    return ret;
}
int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    memset(ans,-1,sizeof ans);

    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++){
        scanf("%d", a + i); --a[i];
        corrsponds[a[i]].push_back(i);
    }

    for(int i = 0; i < n; i++)
        scanf("%d", cap + i);
    scanf("%d", &k);

    for(int i = 0; i < k; i++)
        scanf("%d%d%d", l + i, r + i, add + i), --l[i], --r[i];

    for(int i = 0; i < n; i++){
        hi[i] = k;
        qu[0][(lo[i]+hi[i]) >> 1].push_back(i);
    }


    for(int i = 0; i < 20; i++){
//        cerr << "Search : " << i << '\n';
        for(int j = 0; j < k; j++)qu[i&1^1][j].clear();
        for(int j = 0; j < k; j++){
            if(l[j] <= r[j])
                upd(l[j]+1,r[j]+1,add[j]);
            else
                upd(l[j]+1,off-1,add[j]),
                upd(0,r[j]+1,add[j]);
            for(auto v : qu[i&1][j]){
                ll sum = 0;
                for(auto x : corrsponds[v]){
                    sum += qry(x);
                    if(sum >= cap[v])break;
                }

                if(sum >= cap[v])
                    hi[v] = j;
                else
                    lo[v] = j + 1;

                if(lo[v] < hi[v])
                    qu[i&1^1][(lo[v]+hi[v])>>1].push_back(v);
            }
        }

        for(int j = 0; j < k; j++){
            if(l[j] <= r[j])
                upd(l[j]+1,r[j]+1,-add[j]);
            else
                upd(l[j]+1,off-1,-add[j]),
                upd(0,r[j]+1,-add[j]);
        }

    }

    for(int i = 0; i < n; i++)
        if(lo[i] == k)
            puts("NIE");
        else
            printf("%d\n", lo[i]+1);


    return 0;
}

Compilation message

met.cpp: In function 'void upd(int, int, int)':
met.cpp:31:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         if(l&1^1)laz[l+1]+=v;
            ~^~
met.cpp: In function 'int main()':
met.cpp:73:39: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         for(int j = 0; j < k; j++)qu[i&1^1][j].clear();
                                      ~^~
met.cpp:93:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     qu[i&1^1][(lo[v]+hi[v])>>1].push_back(v);
                        ~^~
met.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
met.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i); --a[i];
         ~~~~~^~~~~~~~~~~~~
met.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", cap + i);
         ~~~~~^~~~~~~~~~~~~~~
met.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
met.cpp:63:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", l + i, r + i, add + i), --l[i], --r[i];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	22776 KB	Output is correct
2	Correct	35 ms	22900 KB	Output is correct
3	Correct	27 ms	22976 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	22976 KB	Output is correct
2	Correct	28 ms	22976 KB	Output is correct
3	Correct	27 ms	23072 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	321 ms	25392 KB	Output is correct
2	Correct	504 ms	27484 KB	Output is correct
3	Correct	374 ms	27484 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	410 ms	27484 KB	Output is correct
2	Correct	446 ms	27484 KB	Output is correct
3	Correct	538 ms	27492 KB	Output is correct
4	Correct	69 ms	27492 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	259 ms	27492 KB	Output is correct
2	Correct	491 ms	27988 KB	Output is correct
3	Correct	253 ms	27988 KB	Output is correct
4	Correct	387 ms	27988 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	438 ms	27988 KB	Output is correct
2	Correct	465 ms	27988 KB	Output is correct
3	Correct	350 ms	27988 KB	Output is correct
4	Correct	492 ms	28880 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3366 ms	46016 KB	Output is correct
2	Correct	2639 ms	46016 KB	Output is correct
3	Correct	1226 ms	46016 KB	Output is correct
4	Runtime error	4835 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3489 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-