답안 #435287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435287 2021-06-23T07:04:30 Z Cross_Ratio 사탕 분배 (IOI21_candies) C++17
컴파일 오류
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1<<19;
const int INF = 2*1e9;
struct Node {
    int mapl; // how many minimum plus remain?
    int mipl;
    int mare; // how many minimum remain?
    int mire;
    int p;
    bool full;
    bool zero;
    int mac;
    int mic;
    Node() : mapl(0),mipl(INF),mare(0),mire(INF),p(0),full(false),zero(false),mac(-INF),mic(INF){}
    Node(int p1, int r1,int c1) : mapl(p1),mipl(p1),mare(r1),mire(r1),p(0),full(false),zero(false),mac(c1),mic(c1){}
};
Node f(Node x, Node y) {
    Node s;
    s.mapl = max(x.mapl, y.mapl);
    s.mipl = min(x.mipl, y.mipl);
    s.mare = max(x.mare, y.mare);
    s.mire = min(x.mire, y.mire);
    s.mac = max(x.mac,y.mac);
    s.mic = min(x.mic,y.mic);
    return s;
}
Node seg[MAX];
void cons() {
    int i;
    for(i=MAX/2-1;i>0;i--) {
        seg[i] = f(seg[2*i],seg[2*i+1]);
    }
}
void prop(int n, int ns, int ne) {
    if(seg[n].p == 0&&!seg[n].full&&!seg[n].zero) return;
    seg[n].mare += seg[n].p;
    seg[n].mire += seg[n].p;
    seg[n].mapl -= seg[n].p;
    seg[n].mipl -= seg[n].p;
    if(seg[n].full) {
        seg[n].mare = seg[n].mac;
        seg[n].mire = seg[n].mic;
        seg[n].mapl = 0;
        seg[n].mipl = 0;
    }
    if(seg[n].zero) {
        seg[n].mare = 0;
        seg[n].mire = 0;
        seg[n].mapl = seg[n].mac;
        seg[n].mipl = seg[n].mic;
    }
    if(n >= MAX/2) {
        seg[n].p = 0;
        seg[n].zero = false;
        seg[n].full = false;
        return;
    }
    else {
        int i;
        for(i=2*n;i<=2*n+1;i++) {
            seg[i].p += seg[n].p;
            if(seg[i].zero) seg[n].zero = true;
            if(seg[i].full) seg[n].full = true;
        }
        seg[n].p = 0;
        seg[n].zero = false;
        seg[n].full = false;
        return;
    }
}
void add1(int s, int e, int a, int n, int ns, int ne) {
    prop(n,ns,ne);
    if(e<=ns||ne<=s) return;
    if(s<=ns&&ne<=e&&seg[n].mipl>=a) {
        seg[n].p += a;
        prop(n,ns,ne);
        return;
    }
    if(s<=ns&&ne<=e&&seg[n].mapl<=a) {
        seg[n].full = true;
        //seg[n].p += seg[n].mapl;
        prop(n,ns,ne);
        return;
    }
    int mid = (ns + ne) / 2;
    add1(s,e,a,2*n,ns,mid);
    add1(s,e,a,2*n+1,mid,ne);
    if(n<MAX/2) seg[n] = f(seg[2*n],seg[2*n+1]);
}
void add2(int s, int e, int m, int n, int ns, int ne) {
    prop(n,ns,ne);
    if(e<=ns||ne<=s) return;
    if(s<=ns&&ne<=e&&seg[n].mire>=m) {
        seg[n].p -= m;
        prop(n,ns,ne);
        return;
    }
    if(s<=ns&&ne<=e&&seg[n].mare<=m) {
        seg[n].zero = true;
        //seg[n].p -= seg[n].mare;
        prop(n,ns,ne);
        return;
    }
    int mid = (ns + ne) / 2;
    add1(s,e,m,2*n,ns,mid);
    add1(s,e,m,2*n+1,mid,ne);
    if(n<MAX/2) seg[n] = f(seg[2*n],seg[2*n+1]);
}
void propall() {
    int i;
    for(i=1;i<MAX;i++) prop(1,1,1);
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i;
    int a,b,c;
    for(i=0;i<N;i++) {
        cin >> a;
        seg[i+MAX/2] = Node(a,0,a);
    }
    int Q;
    cons();
    cin >> Q;
    for(i=0;i<Q;i++) {
        cin >> a >> b >> c;
        if(c >= 0) {
            add1(a-1,b,c,1,0,MAX/2);
        }
        if(c<0) {
            add2(a-1,b,-c,1,0,MAX/2);
        }
    }
    propall();
    for(i=0;i<N;i++) {
        cout << seg[i+MAX/2].mare << ' ';
    }
}

Compilation message

/usr/bin/ld: /tmp/cchLk9Zi.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNFSzvj.o:candies.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cchLk9Zi.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `distribute_candies(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status