oj.uz

답안 #79603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79603 2018-10-15T05:40:02 Z triplem5ds Meteors (POI11_met) C++14
74 / 100
 6000 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];
ll laz[N<<2];
void push(int node, int s, int e){
    if(s != e){
        laz[node<<1] += laz[node];
        laz[node<<1|1] += laz[node];
        laz[node] = 0;
    }
}
void upd(int node, int s, int e, int l, int r, int v){
    push(node,s,e);
    if(r < s || e < l || l > r)
        return;
    if(l <= s && e <= r){
        laz[node] += v;
        push(node,s,e);
        return;
    }
    int md = (s + e) >> 1;
    upd(node<<1,s,md,l,r,v);
    upd(node<<1|1,md+1,e,l,r,v);
}
ll qry(int node, int s, int e, int idx){
    push(node,s,e);
    if(s==e){
        return laz[node];
    }
    int md = (s+e) >> 1;
    if(idx <= md)
        return qry(node<<1,s,md,idx);
    else
        return qry(node<<1|1,md+1,e,idx);
}
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(1,0,m-1,l[j],r[j],add[j]);
            else
                upd(1,0,m-1,l[j],m-1,add[j]),
                upd(1,0,m-1,0,r[j],add[j]);
            for(auto v : qu[i&1][j]){
                ll sum = 0;
                for(auto x : corrsponds[v]){
                    sum += qry(1,0,m-1,x);
                }
                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(1,0,m-1,l[j],r[j],-add[j]);
            else
                upd(1,0,m-1,l[j],m-1,-add[j]),
                upd(1,0,m-1,0,r[j],-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 'int main()':
met.cpp:85: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:103:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     qu[i&1^1][(lo[v]+hi[v])>>1].push_back(v);
                        ~^~
met.cpp:63: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:66: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:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", cap + i);
         ~~~~~^~~~~~~~~~~~~~~
met.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
met.cpp:75: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 42 ms 22776 KB Output is correct
2 Correct 36 ms 22796 KB Output is correct
3 Correct 36 ms 22892 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 22976 KB Output is correct
2 Correct 36 ms 22976 KB Output is correct
3 Correct 37 ms 23200 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1058 ms 26500 KB Output is correct
2 Correct 1205 ms 29700 KB Output is correct
3 Correct 1166 ms 30388 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1184 ms 30880 KB Output is correct
2 Correct 1226 ms 32096 KB Output is correct
3 Correct 1287 ms 34436 KB Output is correct
4 Correct 198 ms 34436 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 34436 KB Output is correct
2 Correct 1000 ms 37420 KB Output is correct
3 Correct 582 ms 37420 KB Output is correct
4 Correct 1156 ms 38556 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1126 ms 38556 KB Output is correct
2 Correct 1140 ms 39828 KB Output is correct
3 Correct 1151 ms 39828 KB Output is correct
4 Correct 1250 ms 44268 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6024 ms 66560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6103 ms 66560 KB Time limit exceeded
2 Halted 0 ms 0 KB -